【洛谷P3386】【模板】二分图匹配【网络流】

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P3386
求一个二分图的最大匹配。

---

思路：

二分图匹配的模板。可以用匈牙利做。
听说这道题卡$Dinic$，但是还是很轻松的过了。可能是加了当前弧优化的缘故吧。
$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)); //当前弧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) //到达终点{maxflow+=flow;return flow;}int used=0;for (int i=cur[u];~i;i=e[i].next) //当前弧优化{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; }

总结

以上是生活随笔为你收集整理的【洛谷P3386】【模板】二分图匹配【网络流】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。