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;
}