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.zzzyk.com
        for(i=minn;i<maxx;i++)  
        {  
            add(i,i+1,0);  
            add(i+1,i,-1);  
        }  
        printf("%d\n",spfa());  
    }  
    return 0;  
}

补充：软件开发 , C++ ,