首页 > 代码库 > ZOJ 2770 Burn the Linked Camp 差分约束+SPFA

ZOJ 2770 Burn the Linked Camp 差分约束+SPFA

2024-07-13 06:08:31   220人阅读

第一道正儿八经的差分约束题

有排成一列的n个点，首先告诉你每个点的值最多是多少(最少显然要大于0），然后告诉你m段i，j,k，表示第i个点到第j个点的值的和至少有k，问你总和至少为多少。

要注意的是，告诉你的所有关系式都不要忘记建边，一开始漏了大于0的条件调半天o(╯□╰)o

不等式的形式是a-b<=c这样的= =

 1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #include <climits> 6 #include <string> 7 #include <iostream> 8 #include <map> 9 #include <cstdlib>10 #include <list>11 #include <set>12 #include <queue>13 #include <stack>14 15 using namespace std;16 17 typedef long long LL;18 const int maxn = 1000 + 5;19 const int maxm = 50000 + 5;20 const LL INF = LONG_LONG_MAX / 4;21 int v[maxm],w[maxm],first[maxn],nxt[maxm];22 int n,m,C,cnt[maxn],ecnt;23 LL d[maxn];24 bool inq[maxn];25 26 void solve() {27     bool bad = false;28     queue<int> q;29     q.push(n);30     for(int i = 0;i <= n;i++) {31         inq[i] = false;32         d[i] = INF;33         cnt[i] = 0;34     }35     d[n] = 0;36     inq[n] = true;37     cnt[n] = 1;38     while(!q.empty() && !bad) {39         int x = q.front(); q.pop();40         inq[x] = false;41         for(int i = first[x];i != -1;i = nxt[i]) {42             if(d[v[i]] > d[x] + w[i]) {43                 d[v[i]] = d[x] + w[i];44                 if(!inq[v[i]]) {45                     q.push(v[i]);46                     cnt[v[i]]++;47                     inq[v[i]] = true;48                     if(cnt[v[i]] > n + 1) {49                         bad = true; break;50                     }51                 }52             }53         }54     }55     if(bad) puts("Bad Estimations");56     else printf("%lld\n",-d[0]);57 }58 59 void adde(int _u,int _v,int _w) {60     v[ecnt] = _v; w[ecnt] = _w;61     nxt[ecnt] = first[_u];62     first[_u] = ecnt;63     ecnt++;64 }65 66 int main() {67     while(~scanf("%d%d",&n,&m)) {68         ecnt = 0;69         memset(first,-1,sizeof(first));70         memset(nxt,-1,sizeof(nxt));71         for(int i = 1;i <= n;i++) {72            scanf("%d",&C);73            adde(i - 1,i,C);74            adde(i,i - 1,0);75         }76         for(int i = 1;i <= m;i++) {77             int a,b,c; scanf("%d%d%d",&a,&b,&c);78             adde(b,a - 1,-c);79         }80         solve();81     }82     return 0;83 }


联系
我们