论文《为什么很多网络流问题总有整数解》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;}