bzoj 4500: 矩阵【差分约束】

(x,y,z)表示格子(x,y)的值为z，也就是x行+y列加的次数等于z，相当于差分约束的条件，用dfs判断冲突即可。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=2005;

int T,n,m,k,cnt,p,h[N],va[N],f;

bool v[N];

struct qwe

{

	int ne,to,va;

}e[N<<1];

void add(int u,int v,int w)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	e[cnt].va=w;

	h[u]=cnt;

}

bool dfs(int u)

{

	v[u]=1;

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

	{

		if(!v[e[i].to])

		{

			va[e[i].to]=e[i].va-va[u];

			if(!dfs(e[i].to))

				return 0;

		}

		else if(va[e[i].to]!=e[i].va-va[u])

			return 0;

	}

	return 1;

}

int main()

{

	scanf("%d",&T);

	while(T--)

	{

		cnt=0;f=0;

		memset(v,0,sizeof(v));

		memset(h,0,sizeof(h));

		memset(va,0,sizeof(va));

		scanf("%d%d%d",&n,&m,&k);

		for(int i=1,x,y,z;i<=k;i++)

		{

			scanf("%d%d%d",&x,&y,&z);

			add(x,y+n,z);

			add(y+n,x,z);

			p=x;

		}

		for(int i=1;i<=n+m;i++)

			if(!v[i]&&!dfs(i))

			{

				puts("No");

				f=1;

				break;

			}

		if(!f)

			puts("Yes");

	}

	return 0;

}

巴特西

bzoj 4500: 矩阵【差分约束】

最新文章

热门文章