UVALive 4885 Task 差分約束

UVALive 4885 Task 差分約束

題目鏈接：點擊打開鏈接

題意：

有n個任務 m個限制條件

1、task i starts at least A minutes later than task j

表示 i - j >= A

2、task i starts within A minutes of the starting time of task j

表示 i - j <= A

問：每個任務開始的時間。 求一個任意解

思路：

差分約束，對於不等式形如：

點u，v ： 常數C

有： u - v <= C

則從v->u 連一條長度為C的邊。

若有負環則差分約束無解。否則就能求得一個任意解。

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define inf 100000000
#define N 200
#define M 200005
struct node{
	int from, to, dis, nex;
}edge[M];
int head[N], edgenum;
void init(){memset(head, -1, sizeof head); edgenum = 0;}
void add(int u, int v, int d){
	node E = {u, v, d, head[u]};
	edge[edgenum] = E;
	head[u] = edgenum++;
}
int n, m;
int dis[N], inq[N], tim[N];
bool spfa(){
	memset(tim, 0, sizeof tim);
	memset(inq, 0, sizeof inq);
	dis[0] = 0;
	for(int i = 1; i <= n; i++)
	{
		dis[i] = inf;
		add(0, i, 0);
	}
	queueq; q.push(0);
	while(!q.empty())
	{
		int u = q.front(); q.pop(); inq[u] = 0;
		for(int i = head[u]; ~i; i = edge[i].nex)
		{
			int v = edge[i].to;
			if(dis[v] > dis[u] + edge[i].dis)
			{
				dis[v] = dis[u] + edge[i].dis;
				if(!inq[v])
				{
					inq[v] = 1; tim[v]++; q.push(v);
					if(tim[v]>n)return false;
				}
			}
		}
	}
	return true;
}
char s[100];
void eat(int x){while(x--)scanf("%s",s);}
void build(){
    scanf("%d", &m);
	init();
	int a, b, x, i;
	while(m--)
	{
		eat(1);
		scanf("%d", &a);
		eat(2);
		if(s[0] == 'a')
		{
			eat(1);
			scanf("%d", &x);
			eat(4);
			scanf("%d", &b);
			add(a, b, -x);
		}
		else
		{
			scanf("%d", &x);
			eat(7);
			scanf("%d", &b);
			add(b, a, x);
		}
		add(a, b, 0);
	}
}
void solve(){
	build();
	if(spfa() == false) { puts("Impossible."); return ;}
	int minn = dis[1];
	for(int i = 2; i <= n; i++) minn = min(minn, dis[i]);
	minn = -minn +1;
	for(int i = 1; i <= n; i++)
		printf("%d%c", dis[i]+minn, i==n?'\n':' ');
}

int main() {
	int a, b, x, i;
	while(scanf("%d", &n), n){
		solve();
	}
	return 0;
}
/*
2
2
task 1 starts at least 5 minutes later than task 2
task 1 starts within 5 minutes of the starting time of task 2

2
2
task 1 starts at least 6 minutes later than task 2
task 1 starts within 5 minutes of the starting time of task 2

2
2
task 1 starts at least 5 minutes later than task 2
task 1 starts within 6 minutes of the starting time of task 2

2
2
task 2 starts at least 5 minutes later than task 1
task 1 starts within 5 minutes of the starting time of task 2

2
2
task 2 starts at least 0 minutes later than task 1
task 1 starts within 0 minutes of the starting time of task 2

ans:


*/