题意
一个n*m的矩阵，初始值全为0，每一行每一列操作一次可以加1或者减1，问能否操作得到给定矩阵。
分析
- 行和列的分别的加减是可以相互抵消的，因此我们只需要考虑行的加和列的减。
- 对于给定矩阵每一个数\(x\)，假设对应行\(u\)加上\(r_u\)次，对应列\(v\)减去\(c_v\)次，即\(r_u+c_v=x\)，转化为不等式，即
\[r_u-c_v<=x
\\
c_v-r_u<=-x
\]
\\
c_v-r_u<=-x
\]
- 对于这样的不等式，使用差分约束系统转化为图论问题，即建边\((v+n,u,x)\)和\((u,v+n,-x)\)，然后判断是否有解，只需用spfa判负环即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
const int INF=0x3f3f3f3f;
int T,n,m,k,u,v,w;
struct Edge{
int v,w,next;
}e[N];
int cnt,head[N];
void init(){
cnt=0;
memset(head,-1,sizeof(head));
}
void add(int u,int v,int w){
e[cnt]=Edge{v,w,head[u]};
head[u]=cnt++;
}
int vis[N],dis[N];
bool spfa(int s){
for(int i=1;i<=s;i++){
vis[i]=0;
dis[i]=INF;
}
queue<int> q;
q.push(s);
vis[s]++;
dis[s]=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=e[i].next){
int v=e[i].v;
int w=e[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(v);
vis[v]++;
if(vis[v]>s+1){
return true;
}
}
}
}
return false;
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
init();
int s=n+m+1;
for(int i=1;i<s;i++){
add(s,i,0);
}
for(int i=1;i<=k;i++){
scanf("%d%d%d",&u,&v,&w);
add(v+n,u,w);
add(u,v+n,-w);
}
if(spfa(s)){
printf("No\n");
}else{
printf("Yes\n");
}
}
return 0;
}