P3386 【模板】二分图匹配

题目背景

二分图

题目描述

给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数

输入输出格式

输入格式：

第一行，n,m,e

第二至e+1行，每行两个正整数u,v，表示u,v有一条连边

输出格式：

共一行，二分图最大匹配

输入输出样例

输入样例#1：复制

1 1 1

1 1

输出样例#1：复制

说明

n,m \leq 1000n,m≤1000 ， 1 \leq u \leq n1≤u≤n ， 1 \leq v \leq m1≤v≤m

因为数据有坑，可能会遇到 v>mv>m 的情况。请把 v>mv>m 的数据自觉过滤掉。

算法：二分图匹配

code

匈牙利

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<cstdlib>

 using namespace std;

 const int N = ;

 int e[N][N],vis[N],resut[N];

 int n,m,E;

 inline int read() {

     int x = ,f = ;char ch = getchar();

     for (; ch<''||ch>''; ch = getchar())

         if (ch=='-') f = -;

     for (; ch>=''&&ch<=''; ch = getchar())

         x = x*+ch-'';

     return x*f;

 }

 bool dfs(int u) {

     for (int v=; v<=m; ++v) {

         if (e[u][v] && !vis[v]) {

             vis[v] = true;

             if (!resut[v] || dfs(resut[v])) {

                 resut[v] = u;

                 return true;

             }

         }

     }

     return false;

 }

 void xyl() {

     int ans = ;

     for (int i=; i<=n; ++i) {

         memset(vis,false,sizeof(vis));

         if (dfs(i)) ans++;

     }

     printf("%d",ans);

 }

 int main() {

     n = read(),m = read(),E = read();

     for (int i=; i<=E; ++i) {

         int a = read(),b = read();

         if (a >n || b > m) continue;

         e[a][b] = ;

     }

     xyl();

     return ;

 }

更新2018-06-03

 #include<cstdio>

 #include<cstring>

 #include<cctype>

 const int N = ;

 struct Edge{

     int to,nxt;

     Edge() {}

     Edge(int a,int b) {to = a,nxt = b;}

 }e[];

 int head[N],match[N],tot;

 bool vis[N];

 int n,m;

 inline int read() {

     int x = ,f = ;char ch = getchar();

     for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-;

     for (; isdigit(ch); ch=getchar()) x=x*+ch-'';

     return x * f;

 }

 bool dfs(int u) {

     for (int i=head[u]; i; i=e[i].nxt) {

         int v = e[i].to;

         if (!vis[v]) {

             vis[v] = true;

             if (!match[v] || dfs(match[v])) {

                 match[v] = u;

                 return true;

             }

         }

     }

     return false;

 }

 int main () {

     n = read(),m = read();int E = read();

     for (int i=; i<=E; ++i) {

         int u = read(),v = read();

         if (u > n || v > m) continue;

         e[++tot] = Edge(v,head[u]);

         head[u] = tot;

     }

     int ans = ;

     for (int i=; i<=n; ++i) {

         memset(vis,false,sizeof(vis));

         if (dfs(i)) ans++;

     }

     printf("%d",ans);

     return ;

 }

最大流

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int N = ;

 const int INF = 1e9;

 struct Edge{

     int to,nxt,c;

     Edge() {}

     Edge(int x,int y,int z) {to = x,c = y,nxt = z;}

 }e[];

 int q[],L,R,S,T,tot = ;

 int dis[N],cur[N],head[N];

 inline char nc() {

     static char buf[],*p1 = buf,*p2 = buf;

     return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2) ? EOF :*p1++;

 }

 inline int read() {

     int x = ,f = ;char ch=nc();

     for (; ch<''||ch>''; ch=nc()) if(ch=='-')f=-;

     for (; ch>=''&&ch<=''; ch=nc()) x=x*+ch-'';

     return x*f;

 }

 void add_edge(int u,int v,int c) {

     e[++tot] = Edge(v,c,head[u]);head[u] = tot;

     e[++tot] = Edge(u,,head[v]);head[v] = tot;

 }

 bool bfs() {

     for (int i=; i<=T; ++i) cur[i] = head[i],dis[i] = -;

     L = ,R = ;

     q[++R] = S;dis[S] = ;

     while (L <= R) {

         int u = q[L++];

         for (int i=head[u]; i; i=e[i].nxt) {

             int v = e[i].to;

             if (dis[v] == - && e[i].c > ) {

                 dis[v] = dis[u]+;q[++R] = v;

                 if (v==T) return true;

             }

         }

     }

     return false;

 }

 int dfs(int u,int flow) {

     if (u==T) return flow;

     int used = ;

     for (int &i=cur[u]; i; i=e[i].nxt) {

         int v = e[i].to;

         if (dis[v] == dis[u] +  && e[i].c > ) {

             int tmp = dfs(v,min(flow-used,e[i].c));

             if (tmp > ) {

                 e[i].c -= tmp;e[i^].c += tmp;

                 used += tmp;

                 if (used == flow) break;

             }

         }

     }

     if (used != flow) dis[u] = -;

     return used;

 }

 int dinic() {

     int ret = ;

     while (bfs()) ret += dfs(S,INF);

     return ret;

 }

 int main() {

     int n = read(),m = read(),E = read();

     S = n+m+;T = n+m+;

     for (int i=; i<=E; ++i) {

         int u = read(),v = read();

         if (u > n || v > m) continue;

         add_edge(u,v+n,);

     }

     for (int i=; i<=n; ++i) add_edge(S,i,);

     for (int i=; i<=m; ++i) add_edge(i+n,T,);

     int ans = dinic();

     printf("%d",ans);

     return ;

 }

巴特西

P3386 【模板】二分图匹配（匈牙利&最大流）