P3386 【模板】二分图匹配
题目背景
二分图
题目描述
给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数
输入输出格式
输入格式：
第一行，n,m,e
第二至e+1行，每行两个正整数u,v，表示u,v有一条连边
输出格式：
共一行，二分图最大匹配
输入输出样例
说明
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 ;
}