Loading... 借用这道题复习一下差分约束 <!--more--> 题目大意就是，一个长度为$n$的数列，有$m$个限制条件，每个限制条件有$s,t,w$三个整数，表示数列第$s$项到第$t$项的和为$w$。 思路也比较简单，首先这样的题目一看就是差分约束，然后因为差分约束是形如$x_i-x_j\leq c$的式子，所以想办法把题目给的条件转化为差的形式，就变成前缀和，$s_i-s_{j-1}=c$，把每个条件的$j-1$向$i$连接一条边，边权为$c$，但是这样可以发现并没有什么用，因为区间和为$w$还包含一个信息就是$s_{j-1}-s_i=-c$，因此再从$i$向$j-1$连一条边，边权为$-c$，这样如果有正环，每个$s$就可以不断更新，也就是一个假的账本（可以画个图来理解一下），反之则为真的账本。 > P.S. 注意数组大小，边数最多可能有2100条（$n\leq 100,m\leq 1000$） ```cpp #include<bits/stdc++.h> using namespace std; int w, n, m; struct Edge{ int to, nxt, w; }e[4009]; int head[4009], tot; int d[4009], cnt[4009]; bool vis[4009]; void add(int x, int y, int w){ e[++tot].w = w; e[tot].to = y; e[tot].nxt = head[x]; head[x] = tot; } bool spfa(){ queue<int> q; memset(d, 0x3f, sizeof(d)); memset(vis, 0, sizeof(vis)); memset(cnt, 0, sizeof(cnt)); q.push(0); d[0] = 0; while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 1; for(int i = head[x]; i; i = e[i].nxt){ int y = e[i].to, w = e[i].w; if(d[y] > d[x] + w){ d[y] = d[x] + w; cnt[y]++; if(cnt[y] > n + 1){ return 0; } if(!vis[y]){ q.push(y); vis[y] = 1; } } } vis[x] = 0; } return 1; } int main(){ scanf("%d", &w); while(w--){ memset(head, 0, sizeof(head)); memset(e, 0, sizeof(e)); tot = 0; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++){ int x, y, w; scanf("%d%d%d", &x, &y, &w); y++; add(x, y, -w); add(y, x, w); } for(int i = 1; i <= n; i++){ add(0, i, 0); } if(spfa()) printf("true\n"); else printf("false\n"); } return 0; } ``` Last modification：April 9, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏