HDU1534 Schedule Problem

原题链接

题目大意

给定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;
}