首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。