首页 > 代码库 > poj1201差分约束

poj1201差分约束

#include<stdio.h>#include<iostream>#include<string.h>#include<queue>#include<stack>#include<list>#include<stdlib.h>#include<algorithm>#include<vector>#include<map>#include<set>#include <fstream>using namespace std;const int maxn=50005;int n;int head[maxn];int len;int dis[maxn];int vis[maxn];struct Node{    int to;int val;int next;}e[11111111];void add(int from,int to,int val){    e[len].to=to;    e[len].val=val;    e[len].next=head[from];    head[from]=len++;}const int INF=0xfffffff;int Max;int cnt[maxn];int spfa(int x){    for(int i=0;i<=Max;i++)        dis[i]=INF;    memset(vis,0,sizeof(vis));    dis[x]=0;vis[x]=1;    queue<int> q; q.push(x);    while(!q.empty()){        int cur=q.front();q.pop();vis[cur]=0;        for(int i=head[cur];i!=-1;i=e[i].next){            int cc=e[i].to;            if(dis[cc]>dis[cur]+e[i].val){                dis[cc]=dis[cur]+e[i].val;                if(!vis[cc]){                    vis[cc]=1;cnt[cc]++;if(cnt[cc]>n) return 0;                    q.push(cc);                }            }        }    }    return 1;}int main(){    while(cin>>n){        Max=0;        int len=0;memset(head,-1,sizeof(head));        memset(cnt,0,sizeof(cnt));        for(int i=0;i<n;i++){            int a;int b;int c;cin>>a>>b>>c;            if(b>Max) Max=b;a--;add(b,a,-c);        }        for(int i=0;i<=Max-1;i++)            add(i,i+1,1);        for(int i=1;i<=Max;i++)            add(i,i-1,0);        int t=spfa(Max);        if(t) cout<<-dis[0]<<endl;    }    return 0;}