【bzoj4500】【矩阵】【dfs】-白红宇的个人博客

【bzoj4500】【矩阵】【dfs】

发布日期：2021-11-16 15:38:50 浏览次数：1 分类：技术文章

本文共 1393 字，大约阅读时间需要 4 分钟。

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

题解：

设x[i]表示第i行+1的次数和-1的次数的差.

y[i]表示第i列+1的次数和-1的次数的差.

显然我们只需要满足

x[i]+y[j]=c[i][j]

我们可以从x[i]向y[i]连一条边权为c[i][j]的边.

把初始权值赋成1,暴力dfs一遍即可.

代码：

#include
    
     #include
     
      #include
      
       #define N 1010using namespace std;int v,n,m,x,y,T,k,g[N*2],cnt,next[N<<2],point[N<<1];bool f[N*2],ff;struct use{int st,en,v;}e[N<<2];void add(int x,int y,int v){  next[++cnt]=point[x];point[x]=cnt;e[cnt].en=y;e[cnt].v=v;}void dfs(int x){  f[x]=1;if (!ff) return;  for (int i=point[x];i;i=next[i])    if (!f[e[i].en]){      g[e[i].en]=e[i].v-g[x];      dfs(e[i].en);    }    else      if (g[e[i].en]+g[x]!=e[i].v){ff=false;return;}}int main(){  scanf("%d",&T);  while (T--){   memset(point,0,sizeof(point));cnt=0;   memset(f,0,sizeof(f));   scanf("%d%d%d",&n,&m,&k);ff=true;	   for (int i=1;i<=k;i++){     scanf("%d%d%d",&x,&y,&v);     add(x,y+n+1,v);add(y+n+1,x,v);   }   for (int i=1;i<=n+m;i++)     if (!f[i]){       g[i]=1;dfs(i); 	   if (ff==false) break;     }   if (ff) cout<<"Yes"<

转载地址：https://blog.csdn.net/sunshinezff/article/details/51139942 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：【bzoj3130】【SDOI2013】【费用流】【最大流】

下一篇：【bzoj4296】【PA2015】【Mistrzostwa】【bfs+dfs】

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！