首页 > 代码库 > hdu 4888 最大流给出行列和求矩阵
hdu 4888 最大流给出行列和求矩阵
第一步,考虑如何求是否有解。使用网络流求解,每一行和每一列分别对应一个点,加上源点和汇点一共有N+M+2个点。有三类边: 1. 源点 -> 每一行对应的点,流量限制为该行的和 2. 每一行对应的点 -> 每一列对应的点,流量限制为 K 3. 每一列对应的点 -> 汇点,流量限制为该列的和 对上图做最大流,若源点出发的边和到达汇点的边全都满流,则有解,否则无解。若要求构造方案,则 (i,j) 对应的整数就是行 i–> 列 j 的流量。 第二步,考虑解是否唯一。显然,解唯一的充分必要条件是完成最大流后的残余网络没有长度大于 2 的环。所以,判断解的唯一性可使用dfs,注意遍历的时候不可以在走完一条边后马上走其反向边,加此限制检查是否有环即可判断解是否唯一。 至此,全题已解决 #include<stdio.h> #include<string.h> #include<queue> using namespace std; #define inf 0x3fffffff #define N 820 struct node { int u,v,w,next; }bian[N*N*4]; int head[N],yong,dis[N],work[N]; void init(){ yong=0; memset(head,-1,sizeof(head)); } void addbian(int u,int v,int w) { bian[yong].u=u; bian[yong].v=v; bian[yong].w=w; bian[yong].next=head[u]; head[u]=yong++; } void add(int u,int v,int w) { addbian(u,v,w); addbian(v,u,0); } int min(int a,int b) { return a<b?a:b; } int bfs(int s,int t) { memset(dis,-1,sizeof(dis)); queue<int>q; q.push(s); dis[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=bian[i].next) { int v=bian[i].v; if(bian[i].w&&dis[v]==-1) { dis[v]=dis[u]+1; q.push(v); if(v==t) return 1; } } } return 0; } int dfs(int s,int limit,int t) { if(s==t)return limit; for(int &i=work[s];i!=-1;i=bian[i].next) { int v=bian[i].v; if(bian[i].w&&dis[v]==dis[s]+1) { int tt=dfs(v,min(limit,bian[i].w),t); if(tt) { bian[i].w-=tt; bian[i^1].w+=tt; return tt; } } } return 0; } int dinic(int s,int t) { int ans=0; while(bfs(s,t)) { memcpy(work,head,sizeof(head)); while(int tt=dfs(s,inf,t)) ans+=tt; } return ans; } int vis[N],ma[N][N],k; int dfs(int u,int pre) { int i; vis[u]=1; for(i=head[u];i!=-1;i=bian[i].next) { int v=bian[i].v; if(bian[i].w&&v!=pre) { if(vis[v]) return 1; if(dfs(v,u)) return 1; } } vis[u]=0; return 0; } int judge(int n) { int i; for(i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i,-1)) return 1; } return 0; } int main() { int m,f,i,j,s,n,t,suma,sumb; while(scanf("%d%d%d",&n,&m,&k)!=EOF) { s=0;t=n+m+1; init(); suma=0;sumb=0; for(i=1;i<=n;i++) { scanf("%d",&f); suma+=f; add(s,i,f); } for(i=1;i<=m;i++) { scanf("%d",&f); sumb+=f; add(i+n,t,f); } for(i=1;i<=n;i++) for(j=1;j<=m;j++) add(i,j+n,k); if(suma!=sumb) { printf("Impossible\n"); continue; } f=dinic(s,t); // printf("%d\n",f); if(f!=suma) { printf("Impossible\n"); continue; } if(judge(n)) printf("Not Unique\n"); else { printf("Unique\n"); memset(ma,0,sizeof(ma)); for(i=1;i<=n;i++) for(j=head[i];j!=-1;j=bian[j].next) { int v=bian[j].v; if(v>n&&v<=n+m) ma[i][v-n]=bian[j^1].w; } for(i=1;i<=n;i++){ for(j=1;j<=m;j++) { if(j>1) printf(" "); printf("%d",ma[i][j]); } printf("\n"); } } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。