【BZOJ4500】矩阵（差分约束）

【BZOJ4500】矩阵（差分约束）

题面

BZOJ

然而权限题

题解

显然拆分行和列。不妨设这一行/列总共加减的值是\(p\)，那么每一个限制就是两个数的和为一个特定的数。这样子不好做，反正是一个二分图，那么把列的\(p\)变成\(-p\)，这样就变成了差是一个定制，直接差分约束判断一下就好了。

#include<iostream>

#include<cstdio>

using namespace std;

#define MAX 4000

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

bool fl;

struct Line{int v,next,w;}e[MAX<<1];

int h[MAX],cnt=1;

inline void Add(int u,int v,int w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}

int n,m,K,dis[MAX];

bool vis[MAX];

void dfs(int u)

{

	vis[u]=true;

	for(int i=h[u];i;i=e[i].next)

		if(!vis[e[i].v])dis[e[i].v]=dis[u]+e[i].w,dfs(e[i].v);

		else if(dis[e[i].v]!=dis[u]+e[i].w)fl=false;

}

int main()

{

	int T=read();

	while(T--)

	{

		n=read();m=read();K=read();fl=true;

		for(int i=1;i<=n+m;++i)h[i]=0,vis[i]=false,dis[i]=0;cnt=1;

		while(K--)

		{

			int x=read(),y=read(),w=read();

			Add(x,y+n,w);Add(y+n,x,-w);

		}

		for(int i=1;i<=n+m;++i)if(!vis[i])dfs(i);

		puts(fl?"Yes":"No");

	}

	return 0;

}