HDU 4888 Redraw Beautiful Drawings(网络流求矩阵的解)
发布日期:2021-08-26 12:38:26 浏览次数:3 分类:技术文章

本文共 2748 字,大约阅读时间需要 9 分钟。

论文《为什么很多网络流问题总有整数解》http://diaorui.net/archives/189;

参考:http://www.cnblogs.com/yuiffy/p/3929369.html

题意:n*m的矩阵,给出每行的和以及每列的和,判断这样的矩阵是否存在,若存在,是否唯一;若唯一,输出解;

思路:网络流,最大流+判环。网络流常用于求多项式整数解。

#include
#include
#include
using namespace std;const int inf=0x7fffffff;bool found,walked[500010];int t,nr,nc,k,sumr,sumc,ans;int r[500010],c[500010];int an[5005][5005];int head[500100],h[500010],g[500010]; //g[i]为层数为i的节点个数,h[i]为i点的层数int d[500010],augc; //d记录当前弧,augc为增广路容量int cnt,st,ed,flow,n,m; //n个点m条边,flow为最大流struct node{ int v,cap,next;};node e[500010];void add(int x,int y,int z){ e[cnt].v=y; e[cnt].cap=z; e[cnt].next=head[x]; head[x]=cnt++; e[cnt].v=x; e[cnt].cap=0; e[cnt].next=head[y]; head[y]=cnt++;}bool dfs(const int &x,const int &prex) //判环{ int biu=-1; walked[x]=true; for(int i=head[x];i!=-1;i=e[i].next) { if(e[i].v==prex) { biu=i;continue; } if(e[i].cap>0) { if(walked[e[i].v]) return true; if(dfs(e[i].v,x)) return true; } if(biu==-1) head[x]=e[i].next; //走了这条边没发现环,删边 else e[biu].next=e[i].next; biu=i; } walked[x]=false; return false;}void aug(const int &m) //dicnic{ int i,mini,minh=n-1; int augco=augc; if(m==ed){ //当前点为汇点 found=true; flow+=augc; //增加流量 return; } for(i=d[m];i!=-1;i=e[i].next){ //寻找容许边 if(e[i].cap&&h[e[i].v]+1==h[m]) //如果残留量大于0且是容许边 { if(e[i].cap
=n) return; //如果源点层数大于n,则返回 if(found) break; //找到汇点,跳出 augc=augco; //没找到就还原当前的流 } } if(!found){ for(i=head[m];i!=-1;i=e[i].next) { if(e[i].cap&&h[e[i].v]
=1;i--) { if(dfs(i,-1))//将行数作为起始位置判环,若存在环,1~nr中必有点在环中 { ans=2; return; } } ans=1;}int main(){ int i,j,cas; while(scanf("%d%d%d",&nr,&nc,&k)!=EOF) { sumr=sumc=0; for(i=1;i<=nr;i++) { scanf("%d",&r[i]); sumr+=r[i]; } for(i=1;i<=nc;i++) { scanf("%d",&c[i]); sumc+=c[i]; } ans=0; if(sumr==sumc) farm();//和不同,则无解 if(ans==0) printf("Impossible\n"); else if(ans!=1) { printf("Not Unique\n"); } else{ printf("Unique\n"); for(i=1;i<=nr;i++) { if(nc>=1) printf("%d",an[i][nc]); for(j=nc-1;j>=1;j--) { printf(" %d",an[i][j]); }printf("\n"); } } } return 0;}

 

转载于:https://www.cnblogs.com/dashuzhilin/p/4643461.html

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

上一篇:Java锁--公平锁
下一篇:Struts的JSP页面标签<html:errors/>的使用方法

发表评论

最新留言

很好
[***.229.124.182]2024年04月23日 04时24分43秒