[文章目录]
Description
有一个n*m的矩阵，初始每个格子的权值都为0，可以对矩阵执行两种操作：
1. 选择一行， 该行每个格子的权值加1或减1。
2. 选择一列， 该列每个格子的权值加1或减1。
现在有K个限制，每个限制为一个三元组(x,y,c)，代表格子(x,y)权值等于c。问是否存在一个操作序列，使得操作完后的矩阵满足所有的限制。如果存在输出”Yes”，否则输出”No”。n,m<=1000 多组数据T<=5
发现如果矩阵有解，可以构造出使选定行累加权值为0的方案数。方法为：所有行减去选定行的权值，所有列加上选定行的权值。
那么，一个行的权值就确定了，由此开始搜索，判断是否无解。时间复杂度O(T*(n+m+k))
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,k;
int head[2100],to[2100],nxt[2100],f[2100],cnt=0;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
}
int dis[2100];
bool vis[2100];
bool bfs()
{
memset(dis,0,sizeof dis); memset(vis,0,sizeof vis);
static int q[2100]; int x,l,r;
for(int i=1;i<=n;++i) if(!vis[i])
{
vis[i]=1; l=r=1; q[1]=i;
while(l<=r)
{
x=q[l++];
for(int j=head[x];j;j=nxt[j])
{
if(!vis[to[j]]) dis[to[j]]=f[j]-dis[x],q[++r]=to[j],vis[to[j]]=1;
else if(dis[to[j]]+dis[x]!=f[j]) return false;
}
}
}
return true;
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
memset(head,0,sizeof head);
cnt=0; int x,y,z;
while(k--)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y+n,z); add(y+n,x,z);
}
if(bfs()) puts("Yes");
else puts("No");
}
return 0;
}