ZOJ1455

题意：给定N个任务，每个任务有一个完成时间。这些任务之间有完成的四种先后顺序，假设这种二元关系建立在x，y之间：
　　　SAS：x至少在y开始时开始
　　　SAF：x至少在y完成时开始
　　　FAS：x至少在y开始时完成
　　　FAF：x至少在y完成时完成
　　　现在问这些任务在最短时间内都被完成的任务安排如何？输出每个任务开始的时刻，如果不能的话输出impossible。

最长路做法：虚拟出一个0点,S0 = 0 ; Si - S0 >= 0 ; 建图如下

for(int i=1; i<=n; i++) InsertEdge(0,i,0);

if(s=="FAS") InsertEdge(v,u,-t[u]);

if(s=="FAF") InsertEdge(v,u,t[v]-t[u]);

if(s=="SAF") InsertEdge(v,u,t[v]);

if(s=="SAS") InsertEdge(v,u,0);

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 using namespace std;
 8 #define N 1005
 9 #define M 1000005
10 #define inf 999999
11 int dis[N],vis[N],head[N],in[N],t[N];
12 int size,n;
13 struct Edge
14 {
15     int v,w,next;
16     Edge(){}
17     Edge(int V,int W,int NEXT):v(V),w(W),next(NEXT){}
18 }edge[M];
19 void Init()
20 {
21     size = 0;
22     memset(head,-1,sizeof(head));
23 }
24 void InsertEdge(int u,int v,int w)
25 {
26     edge[size] = Edge(v,w,head[u]);
27     head[u] = size++;
28 }
29 bool spfa()
30 {
31     for(int i=0; i<=n; i++)
32     {
33         dis[i] = -inf; vis[i] = 0; in[i] = 0 ; 
34     }
35     queue<int> Q;
36     while(!Q.empty()) Q.pop();
37     vis[0] = 1 ; dis[0] = 0 ; in[0] = 1;
38     Q.push(0);
39     while(!Q.empty())
40     {
41         int u = Q.front();
42         Q.pop();
43         vis[u] = 0;
44         for(int i=head[u]; i!=-1 ; i=edge[i].next)
45         {
46             int v = edge[i].v;
47             if(dis[v] < dis[u] + edge[i].w)
48             {
49                 dis[v] = dis[u] + edge[i].w ;
50                 if(!vis[v])
51                 {
52                     vis[v] = 1;
53                     in[v]++;
54                     if(in[v]>(n+1)) return 0;
55                     Q.push(v);
56                 }
57             }
58         }
59     }
60     return 1;
61 }
62 
63 int main()
64 {
65     int cas = 1;
66     while(scanf("%d",&n)&&n)
67     {
68         Init();
69         for(int i=1; i<=n; i++)
70         {
71             scanf("%d",&t[i]);
72         }
73         string s;
74         int u,v;
75         while(cin>>s&&s[0]!='#')
76         {
77             scanf("%d%d",&u,&v);
78             if(s=="FAS") InsertEdge(v,u,-t[u]);
79             if(s=="FAF") InsertEdge(v,u,t[v]-t[u]);
80             if(s=="SAF") InsertEdge(v,u,t[v]);
81             if(s=="SAS") InsertEdge(v,u,0);
82         }
83         for(int i=1; i<=n; i++)
84         {
85             InsertEdge(0,i,0);
86         }
87         printf("Case %d:
",cas++);
88         if(!spfa()) printf("impossible
");
89         else 
90         {
91             for (int i = 1; i <= n; ++i) 
92             {
93                 printf("%d %d
", i, dis[i]);
94             }
95         }
96         printf("
");
97     }
98     return 0;
99 }

View Code

最短路的做法：，之后再虚拟出一个任务0，这个任务必须在每个任务完成后完成，因此在0到每个任务之间添加一条边，

最后计算出所有节点中到0点最迟的开始的任务(Si-S0<=-t[i])，设该任务0点开始，并让每个任务的开始时间都加上这个时间差。

参考了沐阳大牛的链接：http://www.cnblogs.com/Lyush/archive/2013/03/20/2971744.html

for(int i=1; i<=n; i++) InsertEdge(0,i,-t[i]);

if(s=="FAS") InsertEdge(u,v,t[u]);

if(s=="FAF") InsertEdge(u,v,t[u]-t[v]);

if(s=="SAF") InsertEdge(u,v,-t[v]);

if(s=="SAS") InsertEdge(u,v,0);

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <queue>
  7 using namespace std;
  8 #define N 1005
  9 #define M 1000005
 10 #define inf 999999
 11 int dis[N],vis[N],head[N],in[N],t[N];
 12 int size,n;
 13 struct Edge
 14 {
 15     int v,w,next;
 16     Edge(){}
 17     Edge(int V,int W,int NEXT):v(V),w(W),next(NEXT){}
 18 }edge[M];
 19 void Init()
 20 {
 21     size = 0;
 22     memset(head,-1,sizeof(head));
 23 }
 24 void InsertEdge(int u,int v,int w)
 25 {
 26     edge[size] = Edge(v,w,head[u]);
 27     head[u] = size++;
 28 }
 29 bool spfa()
 30 {
 31     for(int i=0; i<=n; i++)
 32     {
 33         dis[i] = inf; vis[i] = 0; in[i] = 0 ; 
 34     }
 35     queue<int> Q;
 36     while(!Q.empty()) Q.pop();
 37     vis[0] = 1 ; dis[0] = 0 ; in[0] = 1;
 38     Q.push(0);
 39     while(!Q.empty())
 40     {
 41         int u = Q.front();
 42         Q.pop();
 43         vis[u] = 0;
 44         for(int i=head[u]; i!=-1 ; i=edge[i].next)
 45         {
 46             int v = edge[i].v;
 47             if(dis[v] > dis[u] + edge[i].w)
 48             {
 49                 dis[v] = dis[u] + edge[i].w ;
 50                 if(!vis[v])
 51                 {
 52                     vis[v] = 1;
 53                     in[v]++;
 54                     if(in[v]>(n+1)) return 0;
 55                     Q.push(v);
 56                 }
 57             }
 58         }
 59     }
 60     return 1;
 61 }
 62 
 63 int main()
 64 {
 65     int cas = 1;
 66     while(scanf("%d",&n)&&n)
 67     {
 68         Init();
 69         for(int i=1; i<=n; i++)
 70         {
 71             scanf("%d",&t[i]);
 72         }
 73         string s;
 74         int u,v;
 75         while(cin>>s&&s[0]!='#')
 76         {
 77             scanf("%d%d",&u,&v);
 78             if(s=="FAS") InsertEdge(u,v,t[u]);
 79             if(s=="FAF") InsertEdge(u,v,t[u]-t[v]);
 80             if(s=="SAF") InsertEdge(u,v,-t[v]);
 81             if(s=="SAS") InsertEdge(u,v,0);
 82         }
 83         for(int i=1; i<=n; i++)
 84         {
 85             InsertEdge(0,i,-t[i]);
 86         }
 87         printf("Case %d:
",cas++);
 88         if(!spfa()) printf("impossible
");
 89         else 
 90         {
 91             int Min = inf, p;
 92             for (int i = 1; i <= n; ++i) 
 93             {
 94                 if (Min > dis[i]) //求出最小的dis[i],也就是最早开始的工作 
 95                 {
 96                     Min = dis[i];
 97                     p = i;
 98                 }
 99             }
100             for (int i = 1; i <= n; ++i) 
101             {
102                 printf("%d %d
", i, dis[i]-dis[p]); //因为求出的dis的值都是负数,所以每个数开始的时间为dis[i]-dis[p] 
103             }
104         }
105         printf("
");
106     }
107     return 0;
108 }

View Code