BZOJ 4500: 矩阵

4500: 矩阵

Time Limit: 1 Sec Memory Limit: 256 MB
Submit: 326 Solved: 182
[Submit][Status][Discuss]

Description

有一个n*m的矩阵，初始每个格子的权值都为0，可以对矩阵执行两种操作：

1. 选择一行，该行每个格子的权值加1或减1。

2. 选择一列，该列每个格子的权值加1或减1。

现在有K个限制，每个限制为一个三元组(x,y,c)，代表格子(x,y)权值等于c。问是否存在一个操作序列，使得操作完后的矩阵满足所有的限制。如果存在输出”Yes”，否则输出”No”。

Input

先输入一个T(T <= 5)代表输入有T组数据，每组数据格式为：

第一行三个整数n, m, k (1 <= n, m,k <= 1000)。

接下来k行，每行三个整数x, y, c。

Output

对于每组数据，输出Yes或者No。

Sample Input

2
2 2 4
1 1 0
1 2 0
2 1 2
2 2 2
2 2 4
1 1 0
1 2 0
2 1 2
2 2 1

Sample Output

Yes
No

HINT

Source

分析：

网格图...嗯，二分图...

对于一个限制$(x,y,c)$就代表$val[x]+val[y]=c$...所以我们$dfs$找到矛盾就好了...

代码：

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

//by NeighThorn

using namespace std;

const int maxn=2000+5;

int n,m,k,cas,cnt,pos,flag,w[maxn],hd[maxn],to[maxn],nxt[maxn],vis[maxn],val[maxn];

inline void add(int x,int y,int s){

	w[cnt]=s;to[cnt]=y;nxt[cnt]=hd[x];hd[x]=cnt++;

}

inline bool dfs(int x,int fa){

	vis[x]=1;

	for(int i=hd[x];i!=-1;i=nxt[i])

		if(!vis[to[i]]){

			val[to[i]]=w[i]-val[x];

			if(!dfs(to[i],x)) return false;

		}

		else if(val[to[i]]!=w[i]-val[x])

			return false;

	return true;

}

signed main(void){

	scanf("%d",&cas);

	while(cas--){

		flag=0;cnt=0;

		memset(hd,-1,sizeof(hd));

		memset(vis,0,sizeof(vis));

		memset(val,0,sizeof(val));

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

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

			scanf("%d%d%d",&x,&y,&s),add(x,y+n,s),add(y+n,x,s),pos=x;

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

			if(!vis[i])

				if(!dfs(i,-1)){

					puts("No");flag=1;break;

				}

		if(!flag) puts("Yes");

	}

	return 0;

}

By NeighThorn

巴特西