poj 1201 Intervals(差分制約)

タイトルリンク:http://poj.org/problem?id=1201
題意:複数の区間[ai,bi]を与え、各区間と集合Sにはci個の同じ要素があり、集合sの中で少なくとも何個の要素があるかを求める.
dis[i]は、ソース点からiまでのすべての要素の中でsと同じ個数を表すと、dis[bi+1]=dis[ai]+ciが得られ、閉区間であるためbi+1がある.
しかし、図の連通性を保証するためには、与えられたデータだけでは不十分であり、テーマには隠れた条件が隠されている.
dis[i+1]-1<=dis[i];
dis[i]<=dis[i+1];
このようにして図を構築することで図の連通を保証することができ,ここで差分制約は最長経路と理解できる.

#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;

const int INF=0x3f3f3f3f;
const int maxn=50010;
int n,m;
int e,head[maxn],dis[maxn];
bool vis[maxn];

struct node{
	int to;
	int w;
	int next;
}edge[150010];

void init(){
	e=0;
	memset(dis,-1,sizeof(dis));
	memset(head,-1,sizeof(head));
}

void addEdge(int u,int v,int w){
	edge[e].to=v,edge[e].w=w,edge[e].next=head[u];
	head[u]=e++;
}

int spfa(int src,int des){
	stack<int>S;
	S.push(src);
	vis[src]=1,dis[src]=0;
	while(!S.empty()){
		int u=S.top();
		S.pop(),vis[u]=0;
		for(int i=head[u];i!=-1;i=edge[i].next){
			int v=edge[i].to;
			if(dis[v]<dis[u]+edge[i].w){
				dis[v]=dis[u]+edge[i].w;
				if(!vis[v]){
					vis[v]=1;
					S.push(v);
				}
			}
		}
	}
	return dis[des];
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
#endif
    while(~scanf("%d",&n)){
    	init();
    	int a,b,c;
    	int src=INF,des=-INF;
    	while(n--){
    		scanf("%d%d%d",&a,&b,&c);
    		addEdge(a,b+1,c);
    		if(a<src) src=a;
    		if(b+1>des) des=b+1;
    	}
    	for(int i=src;i<des;i++){
    		addEdge(i,i+1,0);
    		addEdge(i+1,i,-1);
    	}
    	int ans=spfa(src,des);
    	printf("%d
",ans);
    }
    return 0;
}