poj-1201- Intervals-差分约束问题
搞了很长时间。终于会写差分约束了。若菜伤不起啊~~~
差分约束问题重点：
1，找好约束条件。
2，建图。
3，运用spfa
找约束条件需要看懂题意，多注意隐藏的条件。
建图的时候最起码自己看的懂，能够遍历每一条边。
#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<queue>#define INF 999999;using namespace std;struct list{ int v; int value; int next;};struct list node[151000];int head[100000];int num=1;int maxx,minn;void add(int a,int b,int c){ node[num].v=b; node[num].value=c; node[num].next=head[a]; head[a]=num; num++;}int spfa(){ int dist[100000],i; queue<int>q; for(i=minn;i<=maxx;i++) { dist[i]=-INF; } q.push(minn); dist[minn]=0; while(!q.empty()) { int e; e=q.front(); q.pop(); for(i=head[e];i;i=node[i].next) { if(dist[node[i].v]<dist[e]+node[i].value) { dist[node[i].v]=dist[e]+node[i].value; q.push(node[i].v); } } } return dist[maxx];}int main(){ int n,i,a,b,c; while(~scanf("%d",&n)) { memset(head,0,sizeof(head)); maxx=-INF; minn=INF; num=1; for(i=0;i<n;i++) { cin>>a>>b>>c; if(maxx<b+1)maxx=b+1; if(minn>a)minn=a; add(a,b+1,c); } for(i=minn;i<maxx;i++) { add(i,i+1,0); add(i+1,i,-1); } printf("%d\n",spfa()); } return 0;}