ZOJ 2770 Burn the Linked Camp 差分约束

题意：输入n个营地，告诉你每个营地最多可以有多少人。再告诉你m条记录，告诉你两个营地之间至少有多少人，问你所有营地的人数总和最少是多少。当告诉你的条件有矛盾时输出：Bad Estimations

做法：差分约束，因为给出的条件都是不等式，满足差分约束形式。

每个营地最多x人，则有条件：s[i] - s[i-1] <= x;

i 和 j营地之间至少x人，则有条件：s[j] - s[i-1] >= x; 相当于条件： s[i-1] - s[j] <= -x

为了使整张图联通，不出现断层则有条件：s[i-1] - s[i] <= 0;或者设0为超级原点 s[0] - s[i] <= 0（i= 1 to n）;

具体见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

#define max(a,b) a>b?a:b
#define inf 99999999
const int Max = 1005;

struct node {  
    int v;  
    int len;  
};  
vector<node>map[1005];
int n,m;

int spfa(int s)  
{  
    int i,dis[1005];  
    bool used[1005];  
    int num[1005];  
    queue<int>q;  
    for(i=0;i<1005;i++)  
        dis[i]=inf;  
    memset(num,0,sizeof(num));  
    memset(used,0,sizeof(used));  
    dis[s]=0;  
    used[s]=true;  
    q.push(s);  
    while(!q.empty())  
    {  
        int u=q.front();  
        q.pop();  
        used[u]=false;  
        for(i=0;i<map[u].size();i++)  
        {  
            node p=map[u][i];  
            if(dis[p.v]>dis[u]+p.len)  //bellman算法
            {  
                dis[p.v]=dis[u]+p.len;  
                if(!used[p.v])  //条件有矛盾
                {  
                    used[p.v]=true;  
                    num[p.v]++;  
                    if(num[p.v]>n)  
                        return -1;  
                    q.push(p.v);  
                }  
            }  
        }  
    }  
    return dis[n];  
}  

void init() {  
    int i;  
    for(i=0;i<1005;i++)  
        map[i].clear();  
}  


int main() {
     node p;
    while(scanf("%d%d",&n,&m) == 2) {
        init();
        for(int i = 1; i <= n; i++) {
            int lenth;
            scanf("%d",&lenth);
            p.v = i;
            p.len = 0;
            map[i-1].push_back(p);
            p.v = i-1;
            p.len = lenth;
            map[i].push_back(p);
        }
        bool ok = true;
        int ans;
        for(int i = 0; i < m; i++) {
            int a,b,v;
            scanf("%d%d%d",&a,&b,&v);  
            p.v=b;  
            p.len=-v;  
            map[a-1].push_back(p);
        }
        ans = spfa(0);
        if(ans == -1)
            printf("Bad Estimations\n");
        else
            printf("%d\n",-ans);
    }
    return 0;
}