首页 > 代码库 > POJ 3169 Layout 差分约束

POJ 3169 Layout 差分约束

2024-07-13 08:53:52   227人阅读

做了这道题目感觉对差分约束的理解又加深了一些。

关于差分约束最后要求的值是最大值还是最小值的问题，求最小值的时候可以反向建边求最短路，也可以转化成a-b>=x的约束然后求最长路。求最大值的时候可以直接求最短路，如果目标距离是INF的话就代表可以任意长。

#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 = 10000 + 5;const int maxm = 500000 + 5;const int INF = INT_MAX / 4;int first[maxn],nxt[maxm],d[maxn],v[maxm],w[maxm];int N,ML,MD,qcnt[maxn],ecnt;bool inq[maxn];void adde(int _u,int _v,int _w) {    //printf("adde %d %d %d\n",_u,_v,_w);    v[ecnt] = _v;   w[ecnt] = _w;    nxt[ecnt] = first[_u];    first[_u] = ecnt;    ecnt++;}void solve() {    bool bad = false;    for(int i = 0;i <= N;i++) {        d[i] = INF;        inq[i] = false;        qcnt[i] = 0;    }    d[1] = 0;    inq[1] = true;    queue<int> q;    q.push(1);    qcnt[1] = 1;    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]) {                d[v[i]] = d[x] + w[i];                if(!inq[v[i]]) {                    q.push(v[i]);                    inq[v[i]] = true;                    qcnt[v[i]]++;                    if(qcnt[v[i]] > N + 1) {                        bad = true; break;                    }                }            }        }    }    //for(int i = 0;i <= N;i++) printf("%d ",d[i]); putchar(‘\n‘);    //for(int i = 0;i <= N;i++) printf("%d ",qcnt[i]); putchar(‘\n‘);    if(bad == true) puts("-1");    else if(d[N] >= INF) puts("-2");    else printf("%d\n",d[N]);}int main() {    while(~scanf("%d%d%d",&N,&ML,&MD)) {        ecnt = 0;        memset(first,-1,sizeof(first));        memset(nxt,-1,sizeof(nxt));        for(int i = 1;i <= ML;i++) {            int a,b,c; scanf("%d%d%d",&a,&b,&c);            adde(a,b,c);        }        for(int i = 1;i <= MD;i++) {            int a,b,c; scanf("%d%d%d",&a,&b,&c);            adde(b,a,-c);        }        for(int i = 1;i <= N;i++) {            adde(i,i - 1,0);        }        solve();    }    return 0;}

　　


联系
我们