题目大意
给定n个任务，完成每个任务需要一定的时间，并且任务之间有一定的关系。FAS表示第一个任务需要在第二个任务开始之后完成，FAF表示第一个任务需要在 第二个任务完成之后完成，SAF表示第一个任务需要在第二个任务完成之后开始，SAS表示第一个任务需要在第二个任务开始之后开始。
思路
我们令 start[i] 表示第i个任务的开始时间, cost[i] 表示第i个任务的消耗时间, 那么第 i 个任务的结束时间就应该是 cost[i] + cost[j]
那么根据关系可得:
FAS i j : start[i] + cost[i] >= start[j]
FAF i j : start[i] + cost[i] >= start[j] + cost[j]
SAF i j : start[i] >= start[j] + cost[j],
SAS i j : start[i] >= start[j]
而我们要做的是, 最小化start[i]。 既然是最小化start[i], 那么我们应该把上述的关系是改成start[i] - start[j] >= X 类型的,即:
FAS i j : start[i] - start[j] >= -cost[i]
FAF i j : start[i] - start[j] >= cost[j] - cost[i]
SAF i j : start[i] - start[j] >= cost[j]
SAS i j : start[i] - start[j] >= 0
之后我们只需从 j 建立向 i 的边,以及从 0 向每个节点的边,求一遍最长路就好了
其实还有另外一种做法,可以直接套用最短路模板,把不等式整体乘上 -1 , 这时,所求的最长路就成了最短路(注意建的有向边的方向也会因此改变!)
即:
FAS i j : start[j] - start[i] <= cost[i]
FAF i j : start[j] - start[j] <= cost[i] - cost[j]
SAF i j : start[j] - start[i] <= -cost[j]
SAS i j : start[j] - start[i] <= 0
Code
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxN = 10005;
int n, head[maxN], nowCase, cost[maxN], cnt, vis[maxN], op[maxN], dis[maxN];
class Edge {
public:
int nxt, to, dis;
};
Edge e[maxN << 2];
inline void addEdge(int u, int v, int w)
{
e[++cnt].nxt = head[u]; head[u] = cnt;
e[cnt].to = v; e[cnt].dis = w;
};
inline bool spfa(int st, int ed)
{
memset(vis, 0, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
memset(op, 0, sizeof(op));
queue<int> q;
q.push(st); vis[st] = 1, dis[st] = 0;
while(!q.empty()) {
int now = q.front(); q.pop(); vis[now] = 0; ++op[now];
if(op[now] >= n)
return true;
for(int i = head[now], y; i; i = e[i].nxt) {
if(dis[y = e[i].to] > dis[now] + e[i].dis) {
dis[y] = dis[now] + e[i].dis;
if(!vis[y]) {
vis[y] = 1;q.push(y);
}
}
}
}
return false;
}
int main()
{
while(~scanf("%d", &n)) {
if(n == 0)
break;
cnt = 0;
memset(head, 0 ,sizeof(head));
for(int i = 1; i <= n; ++i)
scanf("%d", &cost[i]);
char mode[10];
while(~scanf("%s", mode)) {
if(mode[0] == '#')
break;
int x, y;
scanf("%d%d", &x, &y);
if(strcmp(mode, "FAF") == 0)
addEdge(x, y, cost[x] - cost[y]);
else if(strcmp(mode, "FAS") == 0)
addEdge(x, y, cost[x]);
else if(strcmp(mode, "SAF") == 0)
addEdge(x, y, -cost[y]);
else if(strcmp(mode, "SAS") == 0)
addEdge(x, y, 0);
}
for(int i = 1; i <= n; ++i)
addEdge(0, i, 0);
bool isFailed = spfa(0, n + 1);
/*
for(int k = 1; k <= n; ++k)
for(int i = head[k]; i; i = e[i].nxt)
printf("%d %d %d\n",k, e[i].to, e[i].dis);
*/
printf("Case %d:\n", ++nowCase);
if(isFailed)
printf("impossible\n");
else {
int minT = 0x3f3f3f3f;
for(int i = 1; i <= n; ++i)
minT = min(minT, dis[i]);
for(int i = 1; i <= n; ++i)
printf("%d %d\n", i, dis[i] - minT);
}
printf("\n");
}
return 0;
}
