首页 > 代码库 > POJ 1364 King 差分约束 找负环

POJ 1364 King 差分约束 找负环

2024-07-13 06:33:17   223人阅读

嘛，虽然是一道水题+模板题，不过还是学到了很多东西的，记录一下。

首先题目给出的不等式是小于，但是差分约束系统只能处理小于等于的情况，所以要转化成小于等于的进行处理。对于整数处理方法非常简单= =

然后是找负环的情况，其实不需要考虑图连不连通，只要一开始就把所有的点的d置成0，然后都push进队列里面就好了。

PS：这种方法同样可以用在处理多源点最短路问题上。

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;const int maxn = 105;const int maxm = 5005;int first[maxn],nxt[maxm],v[maxm],w[maxm];int d[maxn],n,m,ecnt,cnt[maxn];bool inq[maxn];void adde(int _u,int _v,int _w) {    v[ecnt] = _v; w[ecnt] = _w;    nxt[ecnt] = first[_u];    first[_u] = ecnt;    ecnt++;}void solve() {    bool bad = false;    queue<int> q;    for(int i = 0;i <= n;i++) {        d[i] = 0;        cnt[i] = 1;        inq[i] = true;        q.push(i);    }    while(!q.empty() && !bad) {        int x = q.front(); q.pop();        inq[x] = false;        for(int i = first[x];i != -1;i = nxt[i]) {            if(d[v[i]] > d[x] + w[i]) {                if(!inq[v[i]]) {                    inq[v[i]] = true;                    cnt[v[i]]++;                    q.push(v[i]);                    if(cnt[v[i]] > n + 2) {                        bad = true;                        break;                    }                }                d[v[i]] = d[x] + w[i];            }        }    }    if(bad) puts("successful conspiracy");    else puts("lamentable kingdom");}int main() {    while(scanf("%d",&n),n) {        ecnt = 0;        char sig[16];        scanf("%d",&m);        memset(first,-1,sizeof(first));        memset(nxt,-1,sizeof(nxt));        for(int i = 0;i < m;i++) {            int a,b,c;            scanf("%d %d %s %d",&a,&b,sig,&c);            if(sig[0] == ‘g‘) adde(b + a,a - 1,-c - 1);            else adde(a - 1,b + a,c - 1);        }        /*        for(int i = 1;i <= n;i++) {            adde(i,i - 1,0);        }        */        solve();    }    return 0;}

　　


联系
我们