題目大意：

題目鏈接：https://www.luogu.org/problemnew/show/P3386
求一個二分圖的最大匹配。

---

思路：

二分圖匹配的模板。可以用匈牙利做。
聽說這道題卡$Dinic$，但是還是很輕松的過了。可能是加了當(dāng)前弧優(yōu)化的緣故吧。
$Dinic$講解鏈接：https://www.luogu.org/blog/ONE-PIECE/wang-lao-liu-jiang-xie-zhi-dinic

---

代碼：

#include <cstdio> #include <cstring> #include <queue> using namespace std;const int N=1010; const int Inf=1e9; int n,m,s,S,T,x,y,tot=1,maxflow,head[N+N],cur[N+N],dep[N+N];struct edge {int next,to,flow; }e[N*N];void add(int from,int to,int flow) {e[++tot].to=to;e[tot].flow=flow;e[tot].next=head[from];head[from]=tot; }bool bfs() {memset(dep,0x3f3f3f3f,sizeof(dep));memcpy(cur,head,sizeof(cur)); //當(dāng)前弧queue<int> q;dep[S]=1;q.push(S);while (q.size()) //分層{int u=q.front();q.pop();for (int i=head[u];~i;i=e[i].next){int v=e[i].to;if (dep[v]>dep[u]+1&&e[i].flow){dep[v]=dep[u]+1;q.push(v);}}}return dep[T]<Inf; //可以流到終點 }int dfs(int u,int flow) {int low=0;if (u==T) //到達(dá)終點{maxflow+=flow;return flow;}int used=0;for (int i=cur[u];~i;i=e[i].next) //當(dāng)前弧優(yōu)化{int v=e[i].to;cur[u]=i; //記錄if (e[i].flow&&dep[v]==dep[u]+1){low=dfs(v,min(flow-used,e[i].flow)); //流量if (low){used+=low;e[i].flow-=low;e[i^1].flow+=low;if(used==flow) break; //流滿了}}}return used; //最大流量 }void dinic() {while (bfs())dfs(S,Inf); }int main() {memset(head,-1,sizeof(head));scanf("%d%d%d",&n,&m,&s);for (int i=1;i<=s;i++){scanf("%d%d",&x,&y);if (x>n||y>m) continue;add(x,n+y,1);add(n+y,x,0);}S=n+m+1;T=n+m+2;for (int i=1;i<=n;i++){add(S,i,1);add(i,S,0);}for (int i=1;i<=m;i++){add(i+n,T,1);add(T,i+n,0);}dinic();printf("%d\n",maxflow);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【洛谷P3386】【模板】二分图匹配【网络流】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。