burn the linked camp(差分约束).cpp

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

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

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

bool bellman_ford()
{
	int i,j,k,now,t;
	
	for (i=0;i<n;i++) {
		dist[i] = INT_MAX;
	}
	dist[n] = 0;
	k = SQ.size();
	while (k--) {
		SQ.pop();
	}
	for (i=n;i>=0;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();
			
			if (dist[now] == INT_MAX) {
				continue ;
			}
			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,j,t;

	while (scanf("%d %d",&n,&m)==2) {
		map.resize(n+10);
		for (i=0;i<=n;i++) {
			map[i].clear();
		}
		sum[0] = 0;
		for (i=1;i<=n;i++) {
			scanf("%d",&cap);//0 <= S[i] - S[i-1] <= C[i] 
			map[i-1].push_back( node(i, cap) );
			map[i].push_back( node(i-1, 0) );
			sum[i] = sum[i-1] + cap;
		}
		for (i=0;i<m;i++) {
			int x,y,k;
			scanf("%d %d %d",&x,&y,&k);//k <= S[y] - S[x-1] <= sum[y] - sum[x-1]
			map[y].push_back( node(x-1, -k) );
			map[x-1].push_back( node(y, sum[y]-sum[x-1]) );
		}
		
		if (!bellman_ford()) {
			printf("Bad Estimations\n");
		}
		else {
			printf("%d\n", dist[n] - dist[0]);
		}
	}
}