poj-1201- Intervals-差分約束問題

搞了很長時間。終於會寫差分約束了。若菜傷不起啊~~~ 差分約束問題重點： 1，找好約束條件。 2，建圖。 3，運用spfa 找約束條件需要看懂題意，多注意隱藏的條件。 建圖的時候最起碼自己看的懂，能夠遍歷每一條邊。 [html]   #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);           }  www.2cto.com         for(i=minn;i<maxx;i++)           {               add(i,i+1,0);               add(i+1,i,-1);           }           printf("%d\n",spfa());       }       return 0;   }