设第 i 行操作了 a[i] 次，第 j 列操作了 b[j] 次，则：

a[i] + b[j] = v

可加一，可减一，即 b[j] 可负

等价于 a[i] - b[j] = v

有 k 个这样的等式。看是否全部等式可成立。

方法1：等式变成不等式，差分约束系统？

方法2：带权并查集

#include <bits/stdc++.h>  
#define N 2006
using namespace std; 
int fa[N],dis[N],x[N],y[N],z[N];   
int find(int x) 
{
    if(fa[x]==x)  return x;   
    int rt=find(fa[x]);    
    dis[x]=dis[x]+dis[fa[x]];      
    fa[x]=rt;   
    return rt;      
}
void solve() 
{
    int n,m,k; 
    scanf("%d%d%d",&n,&m,&k);           
    for(int i=1;i<=k;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]), y[i]+=n;    
    for(int i=1;i<=n+m;i++) fa[i]=i, dis[i]=0;    
    for(int i=1;i<=k;i++)
    {
        int fx=find(x[i]), fy=find(y[i]);   
        if(fx!=fy) 
        {   
            fa[fx]=fy;   
            dis[fx]=dis[y[i]]-dis[x[i]]+z[i];               
        }  
        else if(dis[x[i]]-dis[y[i]]!=z[i])
		{
			puts("No");
			return;
		} 
    }  
    puts("Yes"); 
}
int main() 
{  
    int T; 
    scanf("%d",&T); 
    while(T--) solve(); 
    return 0; 
}

wahning 讲了做法了

我来补一下 方法1 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;

inline int read(){
	int x=0,f=1; char c=getchar();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}

int T,n,m,k;

struct edge{
	int v,w,nxt;
}e[10004];
int head[2003],tot;
void add_edge(int u,int v,int w){
	e[++tot]=(edge){v,w,head[u]};
	head[u]=tot;
}

int dis[2003],cnt[2003]; bool vis[2003];
queue<int> q;
bool spfa(int s){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(cnt,0,sizeof(cnt));
	dis[s]=0; vis[s]=1;
	q.push(s);
	while (!q.empty()){
		int u=q.front(); q.pop();
		vis[u]=0;
		for (int i=head[u];i;i=e[i].nxt){
			int v=e[i].v, w=e[i].w;
			if (dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if (!vis[v]){
					vis[v]=1; q.push(v);
					++cnt[v];
					if (cnt[v]>=n+m+1){
						return 0;
					}
				}
			}
		} 
	}
	return 1;
}

int main(){
//	freopen("D.in","r",stdin);
	T=read();
	while (T--){
		memset(head,0,sizeof(head)); tot=0;
		n=read();m=read();k=read();
		for (int i=1;i<=k;i++){
			int u=read(),v=read(),w=read();
			add_edge(u,n+v,w);
			add_edge(n+v,u,-w);
		}
		for (int i=1;i<=n+m;i++){
			add_edge(0,i,0);
		}
		
		if (spfa(0)){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}
	
	return 0;
}