首页 > 代码库 > hdu4888 多校B 最大流以及最大流唯一判断+输出方案
hdu4888 多校B 最大流以及最大流唯一判断+输出方案
题意,给一个矩阵,告诉你每行和、每列和,并且限制所填数不大于k,问矩阵是否唯一。
经典建图不说了,第一次遇到判断最大流唯一性的,学习了:用dfs来判断残网中是否还存在环,若存在,则表明绕这个环走一圈,(流一圈流量),还是最大流保持不变,说明还有解。输出方案就EASY了。
WA了一天:第一TLE,因为这题卡DINIC,我的没有优化,后来在zz1215学长加了一行代码,在增广的时候,若发现最小总流量已经为0,则标记该点层-1(不必要往下)。效果显著。原因2:判断环的时候,dfs判断环写错有木有!不可原谅a!每次枚举每个入口点(感觉可以优化),判断环,遇到子孩子是祖先就证明有环。
#include<cstdio> //600ms #include<iostream> #include<queue> #include<cstring> #include<string> using namespace std; const int maxv=910; const int maxe=405*405*2+450; const int inf=0x3f3f3f3f; int n,m,k;int allsumn=0,allsumm=0; int nume=0;int e[maxe][4];int head[maxv]; int nsum[405];int msum[405]; bool flag; void inline adde(int i,int j,int c) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume; e[nume++][2]=c; e[nume][0]=i;e[nume][1]=head[j];head[j]=nume; e[nume++][2]=0; } int lev[maxv];int vis[maxv]; int ss=0;int tt=0; bool bfs() { memset(lev,0,sizeof(lev)); memset(vis,0,sizeof(vis)); queue<int>q; q.push(ss); vis[ss]=1; while(!q.empty()) { int cur=q.front(); q.pop(); for(int i=head[cur];i!=-1;i=e[i][1]) { int v=e[i][0]; if(e[i][2]>0&&!vis[v]) { lev[v]=lev[cur]+1; // if(v==tt)return 1; //这句不加,速度更快 q.push(v); vis[v]=1; } } } return vis[tt]; } int dfs(int u,int minf) { if(u==tt||minf==0)return minf; int sumf=0,f; for(int i=head[u];i!=-1&&minf;i=e[i][1]) { int v=e[i][0]; if(lev[v]==lev[u]+1&&e[i][2]>0) { f=dfs(v,e[i][2]<minf?e[i][2]:minf); sumf+=f; e[i][2]-=f;e[i^1][2]+=f; minf-=f; } } if(!sumf)lev[u]=-1; //关键优化! return sumf; } int dinic() { int sum=0; while(bfs()) sum+=dfs(ss,inf); return sum; } void init() { allsumm=allsumn=nume=0; memset(head,-1,sizeof(head)); ss=n+m;tt=n+m+1; } void read_build() { for(int j=0;j<n;j++) { scanf("%d",&nsum[j]); allsumn+=nsum[j]; } for(int j=0;j<m;j++) { scanf("%d",&msum[j]); allsumm+=msum[j]; } for(int i=0;i<n;i++) for(int j=0;j<m;j++) { adde(i,j+n,k); } for(int i=0;i<n;i++) { adde(n+m,i,nsum[i]); } for(int i=0;i<m;i++) { adde(i+n,n+m+1,msum[i]); } } bool dfs_getother_ans(int u,int fa) { if(flag)return 1; for(int i=head[u];i!=-1;i=e[i][1]) { int v=e[i][0]; if(v==fa||e[i][2]<=0||v==n+m||v==n+m+1)continue; if(!vis[v]) { vis[v]=1; dfs_getother_ans(v,u); vis[v]=0; //出来的时候标记回来啊! } else { flag=1; return 1; } if(flag)return 1; } return 0; } int ansjz[405][405]; int main() { while(scanf("%d%d%d",&n,&m,&k)!=EOF) { init(); read_build(); if(allsumm!=allsumn) {printf("Impossible\n");continue;} int ans=dinic(); if(ans!=allsumm) { printf("Impossible\n"); } else { flag=0; for(int i=0;i<n;i++) { vis[i]=1; if(dfs_getother_ans(i,-1)) { flag=1; break; } vis[i]=0; } if(flag) printf("Not Unique\n"); else { printf("Unique\n"); for(int i=0;i<=n-1;i++) for(int j=head[i];j!=-1;j=e[j][1]) { if(j%2==0) { ansjz[i][e[j][0]-n]=k-e[j][2]; } } for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(j==m-1)printf("%d\n",ansjz[i][j]); else printf("%d ",ansjz[i][j]); } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。