程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ2770,火燒連營,差分約束

ZOJ2770,火燒連營,差分約束

編輯：C++入門知識

差分約束關鍵在於明白為什麼可以轉化為三角不等式。

還有對於不等式 Xi - Xj <= c,要轉化為邊。

這ZOJ2770自己分析的還是挺正確的。

具體分析不寫了，附個代碼= = 加注釋可能稍微比較亂。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

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 edges;
vector 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 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;
}