UVA522 Schedule Problem

• 题目分析

题面很直白, 不难看出是个差分约束.

这题的特点在于项目各个部分之间的先后关系.
怎么处理呢? 拆点? 好像有点麻烦... 因为题目输入会给出各个部分的时间, 所以其实可以直接用边权表示这种约束.

题目要求总时间最短, 所以应该把约束整理成 (d_x geq d_y + c) 的形式然后跑最长路.

建图如下:

Len[i]表示第 i 部分的时间

Add(u, v, -Len[v]); //FAS
Add(u, v, Len[u] - Len[v]); //FAF
Add(u, v, Len[u]); //SAF
Add(u, v, 0); //SAS

关于无解情况, 就是 SPFA 找到了正环.
另外注意输出格式, 每组输出间要有空行.

• 代码

#include <cstdio>
#include <queue>
#include <iostream>
#include <string>
#include <cstring>

const int N = 1e5;
const int M = 1e6;
int Dis[N + 5], Head[N + 5], Len[N + 5], n, m;
struct Edge {int To, Nxt, Val;} S[M + 5];
int Cnt_Vis[N + 5], Cnt;
bool Vis[N + 5];

bool SPFA();
void Add(int, int, int);

int main() {
	std::ios::sync_with_stdio(false);

	int tap_Cnt = 0;
	while(std::cin >> n) {
		++tap_Cnt;
		std::cout << "Case " << tap_Cnt << ":";
		for(int i = 1; i <= n; i ++) std::cin >> Len[i];
		while(true) {
			int u, v;
			std::string tap;
			std::cin >> tap;
			if(tap[0] == '#') break;
			std::cin >> u >> v;
			if(tap[0] == 'F' && tap[2] == 'S') Add(u, v, -Len[v]);
			if(tap[0] == 'F' && tap[2] == 'F') Add(u, v, Len[u] - Len[v]);
			if(tap[0] == 'S' && tap[2] == 'F') Add(u, v, Len[u]);
			if(tap[0] == 'S' && tap[2] == 'S') Add(u, v, 0);
		
		} if(!SPFA()) std::cout << "
impossible";
		else for(int i = 1; i <= n; i ++) 
			std::cout << "
" << i << " " << Dis[i];
		std::cout << "

";
		memset(Head, 0, sizeof(Head)), Cnt = 0;
	} return 0;

} void Add(int u, int v, int w) {
    ++Cnt;
    Cnt[S].Val = w, Cnt[S].To = v;
    Cnt[S].Nxt = u[Head], u[Head] = Cnt;
    
} bool SPFA() {
	memset(Dis, 0, sizeof(Dis));
	memset(Cnt_Vis, 0, sizeof(Vis));
	memset(Vis, false, sizeof(Vis));

    std::queue<int> Q;
    for(int i = 1; i <= n; i ++) Q.push(i), Vis[i] = true, Cnt_Vis[i] = 1;

    while(Q.size()) {
        int tap = Q.front();
        Q.pop(), tap[Vis] = false;
        for(int i = tap[Head]; i; i = i[S].Nxt) {
            int v= i[S].To;
            if(v[Dis] < tap[Dis] + i[S].Val) {
                v[Dis] = tap[Dis] + i[S].Val;
                if(!v[Vis]) {
                    if((++v[Cnt_Vis]) >= n) return false;
                    v[Vis] = true, Q.push(v);
                }
            }
        }
    } return true;
}