学步园

HDOJ上拥塞了大量国人的英文题，每每做题都深感自己的英文知识在受误导。囧了个囧。于是ZOJ和POJ上见个外国佬的英文题就认认真真当阅读理解诚惶诚恐读之。

这个题构建tim数组表示第i个任务结束的时间，据此列出三角不等式【事后证明tim表示第i个任务的开始时间才是明智的，SB了】。

const int sup = 1010;//边的数目<br /> struct node<br /> {<br /> int v;<br /> int w;<br /> node *nxt;<br /> }ede[sup << 3], back[sup << 3];//边好多<br /> const int INF = ~(1 << 31);<br /> int ct;<br /> bool vis[sup];<br /> int dis[sup];<br /> int n;<br /> inline void add_ede(int u, int v, int w)<br /> {<br /> node *tp = &back[++ ct];<br /> tp ->v = v;<br /> tp ->w = w;<br /> tp ->nxt = ede[u].nxt;<br /> ede[u].nxt = tp;<br /> }<br /> int in[sup];//记录每个节点出入的次数，大于n时表示存在负环<br /> bool spfa(int st, int ed)//求最长路<br /> {<br /> for(int i = 0; i<= n; ++ i) dis[i] = INF;<br /> dis[st] = 0;<br /> memset(in, 0, sizeof(in));<br /> memset(vis, 0, sizeof(vis));<br /> queue <int> Q;<br /> Q.push(st);<br /> ++ in[st];<br /> while(!Q.empty())<br /> {<br /> int tp = Q.front();<br /> Q.pop();<br /> vis[tp] = false;<br /> for(node *i = ede[tp].nxt; i; i = i ->nxt)<br /> {<br /> int w = i ->w;<br /> if(dis[i ->v] > dis[tp] + w)<br /> {<br /> dis[i ->v] = dis[tp] + w;<br /> if(!vis[i ->v])<br /> {<br /> vis[i ->v] = true;<br /> Q.push(i ->v);<br /> ++ in[i ->v];<br /> if(in[i ->v] > n + 1) return false;<br /> }<br /> }<br /> }<br /> }<br /> return true;<br /> }<br /> int ned[sup];<br /> int tim[sup];//tim[i]表示完成i部分的时刻【也可以更简单的设为开始时刻】<br /> int main()<br /> {<br /> //freopen("1.txt", "w", stdout);<br /> char opt[5];<br /> int a, b;<br /> for(int pz = 1; scanf("%d", &n) && n; ++ pz)<br /> {<br /> ct = 0;<br /> for(int i = 0; i <= n; ++ i) ede[i].nxt = NULL;<br /> for(int i = 1; i <= n; ++ i) scanf("%d", ned + i);<br /> while(scanf("%s", opt), '#' != opt[0])<br /> {<br /> scanf("%d %d", &a, &b);<br /> if('F' == opt[0])//<br /> {<br /> //FAS a要在b开始后结束 tim[a] >= tim[b] - ned[b]<br /> //tim[b] - tim[a] <= ned[b]<br /> if('S' == opt[2]) add_ede(b, a, ned[b]);<br /> //FAF a要在b结束后结束 tim[a] >= tim[b]<br /> //tim[b] - tim[a] <= 0<br /> else if('F' == opt[2]) add_ede(b, a, 0);<br /> }<br /> else if('S' == opt[0])<br /> {<br /> //SAF a要在b结束后开始 tim[a] - ned[a] >= tim[b]<br /> //tim[b] - tim[a] <= -ned[a]<br /> if('F' == opt[2]) add_ede(b, a, -ned[a]);<br /> //SAS a要在b开始后开始 tim[a] - ned[a] >= tim[b] - ned[b]<br /> //tim[b] - tim[a] <= ned[b] - ned[a]<br /> else if('S' == opt[2]) add_ede(b, a, ned[b] - ned[a]);<br /> }<br /> }<br /> for(int i = 1; i <= n; ++ i) add_ede(0, i, -ned[i]);//直接开始第i项任务耗时ned[i]<br /> /*if(1 == pz)*/ printf("Case %d:/n", pz);<br /> //else printf("/nCase %d:/n", pz);<br /> if(!spfa(0, n))<br /> {<br /> puts("impossible/n");<br /> continue;<br /> }<br /> for(int i = 1; i <= n; ++ i) printf("%d %d/n", i, dis[0] - dis[i] - ned[i]);<br /> puts("");<br /> }//最后一个case后还要输出一个空行<br /> return 0;<br /> }