Loading... 这又是一道差分约束 <!--more--> 和P2294基本上没区别，代码甚至和上一个文章的代码一模一样，记一下思路吧 一个矩阵，n行m列，有两种操作，某行或者某列同时加减一个数，然后有些位置有固定的数，给出某些位置的数，问能否通过一些操作使得这些位置上的数能满足要求。 给出第x行第y列的数为c，就相当于第x行的操作数加上（减去）第y行操作数等于c就行了，正好符合差分约束条件，判个负环就行。 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int n, m, k; struct Edge{ int to, nxt; ll w; }e[4000009]; int head[2009], tot; ll dis[2009]; int cnt[2009]; bool vis[2009]; void add(int x, int y, ll w){ e[++tot].to = y; e[tot].w = w; e[tot].nxt = head[x]; head[x] = tot; } bool spfa(){ queue<int> q; memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); memset(cnt, 0, sizeof(cnt)); dis[0] = 0; q.push(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; ll w = e[i].w; if(dis[y] > dis[x] + w){ dis[y] = dis[x] + w; cnt[y]++; if(cnt[y] > n + m){ return 0; } if(!vis[y]){ q.push(y); vis[y] = 1; } } } vis[x] = 0; } return 1; } int main(){ int T; scanf("%d", &T); while(T--){ scanf("%d%d%d", &n, &m, &k); memset(head, 0, sizeof(head)); memset(e, 0, sizeof(e)); tot = 0; for(int i = 1; i <= k; i++){ int x, y; ll w; scanf("%d%d%lld", &x, &y, &w); y = n + y; add(x, y, w); add(y, x, -w); } for(int i = 1; i <= n + m; i++) add(0, i, 0); if(spfa()) printf("Yes\n"); else printf("No\n"); } return 0; } ``` Last modification：April 11, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏