intervals(差分约束).cpp

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

//那么如果在一个未知数定死的情况下，要求其它所有未知数的最小值怎么办？
//只要反过来求最长路径就可以了。最长路径中的三角不等式与最短路径中相反：

//d(v) >= d(u) + w(u, v) 
//也就是 d(v) - d(u) >= w(u, v)

#include <cstdio>
#include <string>

struct node {
	int s,e,v;
}edge[51000];
int n,dist[51000],nmax,nmin;

int bellman_ford()
{
	int i,j;
	bool flag;
	dist[nmin] = 0;
	for (i=0;i<nmax-nmin;i++) {
		flag = false;
		for (j=0;j<n;j++) {
			if (dist[edge[j].s]!=-1 && dist[edge[j].s] + edge[j].v > dist[edge[j].e] ) {
				dist[edge[j].e] = dist[edge[j].s] + edge[j].v;
				flag = true;
			}
		}
		for (j=nmin;j<nmax;j++) {
			if (dist[j]!=-1 && dist[j] > dist[j+1]) {
				dist[j+1] = dist[j];
				flag = true;
			}
		}
		for (j=nmax;j>nmin;j--) {
			if (dist[j]!=-1 && dist[j]-1 > dist[j-1]) {
				dist[j-1] = dist[j] -1;
				flag = true;
			}
		}
		//for (j=nmin;j<=nmax;j++) {
			//printf("[%d]=%d, ",j,dist[j]);
		//}

		if (!flag) {
			break ;
		}
	}
	return dist[nmax];
}

int main()
{
	int i,j;
	while (scanf("%d",&n)==1) {
		nmin = 99999;
		nmax = -1;
		memset(dist,-1,sizeof(dist));
		for (i=0;i<n;i++) {
			scanf("%d %d %d",&edge[i].s, &edge[i].e, &edge[i].v);
			edge[i].e ++;//important
			if (edge[i].s < nmin) {
				nmin = edge[i].s;
			}
			if (edge[i].e > nmax) {
				nmax = edge[i].e;
			}
		}
		printf("%d\n",bellman_ford());
		
	}
}