ZOJ2770,火烧连营,差分约束

差分约束关键在于明白为什么可以转化为三角不等式。

还有对于不等式   Xi - Xj <= c,要转化为边<Vj, Vi>。

这ZOJ2770自己分析的还是挺正确的。

具体分析不写了，附个代码= =  加注释可能稍微比较乱。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define clr(x) memset(x,0,sizeof(x))
#define fp1 freopen("in.txt","r",stdin)
#define fp2 freopen("out.txt","w",stdout)
#define pb push_back

#define INF 0x3c3c3c3c3c
typedef long long  LL;

struct Edge {
    LL from, to, dist;
};

const int maxn = 1e6;

struct BF{       //结点编号应该从0开始。   应该可以不从0开始
int n;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];  //队列优化spfa判断是否边已加入
LL d[maxn];
int p[maxn];    //最短路中的上一条弧
int is_neg[maxn];  //进队次数  用于判断是否有负权环

void init()
{
    for(int i = 0;i <= n;i++) G[i].clear();
    edges.clear();
}

void addedge(LL from, LL to, LL dist)  //单向边操作
{
    //printf("%d %d %d~\n", from, to, dist);
    edges.push_back((Edge){from, to, dist});
    int len = edges.size();
    G[from].push_back(len - 1);
}

int spfa(LL be)  //可返回bool判断负权环
{
    memset(inq, 0, sizeof(inq));
    memset(p, 0, sizeof(p));
    memset(is_neg, 0, sizeof(is_neg));  //注释用于判断负环
    queue<int> Q;
    for(int i = 0;i <= n;i++)
       d[i] = INF;
    d[be] = 0;
    Q.push(be);
    inq[be] = true;

    while(!Q.empty())  //  非空~
    {
        int u = Q.front(); Q.pop();
        inq[u] = false;
        for(int i = 0;i < G[u].size();i++) {
            Edge &e = edges[G[u][i]];
            if(d[e.to] > d[u] + e.dist) {
            //这地方把想要输入的值已经转化为e.dist了
                d[e.to] = d[u] + e.dist;
                p[e.to] = u; //G[u][i]存的是一条边的信息哪不存在标号 直接改成u
                if(!inq[e.to]) {
                    Q.push(e.to);
                    inq[e.to] = true;
                    if(++is_neg[e.to] > n) return false;
                }
            }
            //else...

        }
    }
    return true;
}
}test;

LL sold[1000+10];
LL sum[1000+10];

int main()
{
    //fp1;
    LL n, m, a, b, c;
    while(scanf("%lld %lld", &n, &m) == 2){
        test.n = n;
        test.init();
        clr(sold);
        clr(sum);
        for(int i = 1;i <= n;i++){
            scanf("%lld", &sold[i]);
            sum[i] = sum[i-1] + sold[i];
            test.addedge(i,i-1,0);       //Si - Si-1 > 0 每个兵营的数目不能小于0
            test.addedge(i-1,i,sold[i]); //最多容纳sold[i];
        }
        //puts("-----------------");
        for(int i = 1;i <= m;i++){
            scanf("%lld %lld %lld", &a, &b, &c);
            test.addedge(b,a-1,-c);             //a---b至少有c个人
            //test.addedge(a-1,b,sum[b]-sum[a-1]);  //a---b最多有x人
        }

        if(!test.spfa(n)){
            puts("Bad Estimations");
            //printf("%d\n", test.d[0]);
        }
        else printf("%d\n", -test.d[0]);
//
//          test.n = 3;
//          test.addedge(1,2,5);
//          test.addedge(2,3,6);
//          if(!test.spfa(1)) puts("hehe");
//          else printf("%d %d %d\n",test.d[1],test.d[2],test.d[3]);
     }
    return 0;
}

ZOJ2770,火烧连营,差分约束,布布扣,bubuko.com

ZOJ2770,火烧连营,差分约束

原文：http://blog.csdn.net/cgf1993/article/details/27396003