首页 > 代码库 > hihoCoder 1393 网络流三·二分图多重匹配 (网络流学习#3 记录)
hihoCoder 1393 网络流三·二分图多重匹配 (网络流学习#3 记录)
题目链接:http://hihocoder.com/problemset/problem/1393
话说我之前一直不知道二分匹配可以用网络流做。。。
#include<cstdio>#include<cstring>#include<queue>using namespace std;const int N=205;struct ss{int v,c,nxt;} e[N*20];int head[N],tot,vis[N],n,m,a[N],b[N],sum,INF=0x3f3f3f3f,t;queue<int>q;void add(int u,int v,int c){ e[tot].c=c; e[tot].v=v; e[tot].nxt=head[u]; head[u]=tot++; e[tot].c=0; e[tot].v=u; e[tot].nxt=head[v]; head[v]=tot++;}bool bfs(){ memset(vis,0,sizeof(vis)); vis[0]=1; q.push(0); int tmp,id; while(!q.empty()) { tmp=q.front(); q.pop(); for(int i=head[tmp]; i!=-1; i=e[i].nxt) { id=e[i].v; if(vis[id]==0&&e[i].c) vis[id]=vis[tmp]+1,q.push(id); } } return vis[n+m+1];}int dfs(int node,int c){ if(node==t||c==0) return c; int ans=0; for(int i=head[node]; i!=-1; i=e[i].nxt) { int id=e[i].v,kk; if(vis[id]==vis[node]+1) { kk=dfs(id,min(c,e[i].c)); if(kk>0) { e[i].c-=kk; e[i^1].c+=kk; ans+=kk; c-=kk; if(c==0) return ans; } } } return ans;}int mf(){ int ans=0; while(bfs()) { ans+=dfs(0,INF); } if(ans!=sum) return 0; return 1;}int main(){ int T; scanf("%d",&T); while(T--) { int x=0; memset(head,-1,sizeof(head)); tot=0; sum=0; scanf("%d%d",&n,&m); t=n+m+1; for(int i=1; i<=m; i++) { scanf("%d",&x); add(n+i,t,x); sum+=x; } for(int i=1; i<=n; i++) { scanf("%d%d",&a[i],&b[i]); add(0,i,a[i]); for(int j=0; j<b[i]; j++) { scanf("%d",&x); add(i,x+n,1); } } if(mf()) puts("Yes"); else puts("No"); }}
(邻接表)
昨天邻接表打了一发,然后今天邻接矩阵就卡了,wa了半天,然后发现我初始化有问题,。,。郁闷。
#include<bits/stdc++.h>using namespace std;const int maxn=205,INF=0x3f3f3f3f;int n,m,a[maxn],b[maxn],mm[maxn],s=0,t,c[maxn][maxn],pre[maxn],flow[maxn];int bfs(){ int tmp; memset(pre,-1,sizeof(pre)); memset(flow,0,sizeof(flow)); queue<int>q; q.push(s); flow[s]=INF; while(!q.empty()) { tmp=q.front(); q.pop(); if(tmp==t) return flow[t]; for(int i=1;i<=t;i++) { if(pre[i]==-1&&c[tmp][i]>0) { pre[i]=tmp; flow[i]=min(flow[tmp],c[tmp][i]); if(flow[i]!=0) q.push(i); } } } return 0;}void work(){ int ans=0; int tmp; while(bfs()) { tmp=t; while(tmp!=s) { c[pre[tmp]][tmp]-=flow[t]; c[tmp][pre[tmp]]+=flow[t]; tmp=pre[tmp]; } ans+=flow[t]; } if(ans!=mm[0]) puts("No"); else puts("Yes");}int main(){ int T,tmp; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); t=n+m+1; mm[0]=0; memset(c,0,sizeof(c)); for(int i=1;i<=m;i++) { scanf("%d",&mm[i]); c[n+i][t]+=mm[i]; mm[0]+=mm[i]; } for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); c[s][i]+=a[i]; for(int j=1;j<=b[i];j++) { scanf("%d",&tmp); c[i][n+tmp]+=1; } } work(); }}
(邻接矩阵)
我感觉我现在网络流已经入门了。。。然而还是不知道 什么时候该用哪个,,比如我做下一题的时候就直接用了ek那个我就超时了。。。然后改成分层的。。
hihoCoder 1393 网络流三·二分图多重匹配 (网络流学习#3 记录)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。