schedule problem(差分约束).cpp

杭电acm解题报告2001---2099.

//得用邻接表，不然会超时
#include <cstdio>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 1100

int n,m;
int len[MAX], dist[MAX];
struct node {
	int e,v;
	node(int a=0,int b=0) {
		e = a;
		v = b;
	}
};
queue<int> SQ;
vector<vector<node> > map;

bool bellmax_ford()
{
	int i,j,k,now;

	for (i=0;i<=n;i++) {
		dist[i] = 0;
	}
	k = SQ.size();
	while (k--) {
		SQ.pop();
	}
	for (i=0;i<n;i++) {
		SQ.push(i);
	}

	for (i=0;i<=n+1;i++) {
		k = SQ.size();
		if (k == 0) {
			break ;
		}
		while (k--) {
			now = SQ.front();
			SQ.pop();
			for (j=map[now].size()-1;j>=0;j--) {
				node next = map[now][j];
				if (dist[next.e] > dist[now]+next.v) {//最短路
					dist[next.e] = dist[now]+next.v;
					SQ.push(next.e);
				}
			}
		}
	}//for
	return i<n;
}

int main()
{
	int i,x,y,j,t;
	char cmd[5];
	node edge;
	
	t = 1;
	while (scanf("%d",&n) , n) {
		printf("Case %d:\n",t++);
		map.resize(n+10);
		for (i=map.size()-1;i>=0;i--) {
			map[i].clear();
		}
		for (i=0;i<n;i++) {
			scanf("%d",&len[i]);
		}
		getchar();
		m = 0;
		while (scanf("%s",cmd) ==1) {
			if (cmd[0] == '#') {
				break ;
			}
			scanf("%d %d",&x,&y);
			x --;	y --;
			edge.e = x;
			getchar();
			if (cmd[0] == 'F') {
				if (cmd[2] == 'F') {//FAF S2-S1 >= L1-L2
					edge.v = len[x] - len[y];
				}
				else {//FAS S2-S1 >= L1
					edge.v = len[x];
				}
			}
			else {
				if (cmd[2] == 'F') {//SAF S2-S1 >= -L2
					edge.v = - len[y];
				}
				else {//SAS S2-S1 >= 0
					edge.v = 0;
				}
			}
			map[y].push_back(edge);//S2 -> S1
		}
		
		if (!bellmax_ford()) {
			printf("impossible\n");
		}
		else {
			int mmin = 99999999;
			for (i=0;i<n;i++) {
				dist[i] = - dist[i];//最长路
				if (dist[i] < mmin) {
					mmin = dist[i];
				}
			}
			mmin = 0 - mmin;//从0点开始
			for (i=0;i<n;i++) {
				printf("%d %d\n",i+1,dist[i]+mmin);
			}
		}
		printf("\n");
	}
}