题解 P3386 【【模板】二分图匹配】

suncongbo

2017-11-13 20:34:29

Solution

给两种做法: 1. 匈牙利算法 本质上是贪心 ```cpp #include<cstdio> #include<cstring> using namespace std; const int N = 1e3; bool f[N][N]; bool used[N]; int match[N]; int n,m,e; bool DFS(int pos) { for(int i=1; i<=m; i++) { if(f[pos][i] && !used[i]) { used[i] = true; if(!match[i] || DFS(match[i])) //如果这个点i还未匹配则pos和他匹配,如果这个点已经匹配,那么如果本来和他匹配的点match[i]还能找到另一个点匹配则pos把i“抢”过来,让match[i]去匹配另一个点,否则就不干涉i和match[i]匹配 { match[i] = pos; return true; } } } return false; } int main() { scanf("%d%d%d",&n,&m,&e); for(int i=1; i<=e; i++) { int x,y; scanf("%d%d",&x,&y); if(x<=n && y<=m) f[x][y] = true; } int ans = 0; for(int i=1; i<=n; i++) { memset(used,false,sizeof(used)); //注意此处 if(DFS(i)) ans++; } printf("%d\n",ans); return 0; } ``` 2.网络最大流 建一个点s编号为1为源点,建一个点t编号为n+m+2为汇点。然后让A类点分别编号为2~n+1, B类点分别编号为n+2~n+m+1。 然后建边:把s和所有A类点都连边,AB类点之间根据输入连边,所有B类点和T连边,每条边边权均为1. 最后在图上跑网络最大流即可。 ```cpp #include<cstdio> #include<queue> #include<cstring> using namespace std; const int N = 2005; const int M = 1002005; const int INF = 0x7fffffff; struct Edge { int v,val,nxt,rev; }; Edge e[M<<1]; int fe[N]; queue<int> q; int dep[N]; int n,m,s,t; bool bfs() { while(!q.empty()) q.pop(); memset(dep,0,sizeof(dep)); q.push(s); dep[s] = 1; while(!q.empty()) { int c = q.front(); q.pop(); for(int i=fe[c]; i; i=e[i].nxt) { if(e[i].val>0 && !dep[e[i].v]) { dep[e[i].v] = dep[c]+1; q.push(e[i].v); } } } if(dep[t]) return true; else return false; } int dfs(int pos,int cur) { if(pos==t) return cur; int rst = cur; for(int i=fe[pos]; i; i=e[i].nxt) { if(dep[e[i].v]==dep[pos]+1 && e[i].val>0 && rst) { int flow = dfs(e[i].v,min(e[i].val,rst)); if(flow>0) { e[i].val -= flow; rst -= flow; e[e[i].rev].val += flow; } } } return cur-rst; } int dinic() { int ans = 0; while(bfs()) ans += dfs(s,INF); return ans; } void addedge(int u,int v,int val,int rev) { e[++m].v = v; e[m].val = val; e[m].rev = rev; e[m].nxt = fe[u]; fe[u] = m; } int main() { int n1,n2,m0; m = 0; scanf("%d%d%d",&n1,&n2,&m0); n = n1+n2+2; for(int i=1; i<=m0; i++) { int x,y; scanf("%d%d",&x,&y); if(x<=n1 && y<=n2) { addedge(x+1,y+n1+1,1,m+2); addedge(y+n1+1,x+1,0,m); } } for(int i=1; i<=n1; i++) { addedge(1,i+1,1,m+2); addedge(i+1,1,0,m); } for(int i=1; i<=n2; i++) { addedge(i+n1+1,n,1,m+2); addedge(n,i+n1+1,0,m); } s = 1; t = n; printf("%d\n",dinic()); return 0; } ```