题目背景
二分图
题目描述
给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数
输入输出格式
输入格式：
第一行，n,m,e
第二至e+1行，每行两个正整数u,v，表示u,v有一条连边
输出格式：
共一行，二分图最大匹配
输入输出样例
输入样例#1：
1 1 11 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
匈牙利
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 const int N = 1010;10 int e[N][N],vis[N],resut[N];11 int n,m,E;12 13 inline int read() {14 int x = 0,f = 1;char ch = getchar();15 for (; ch<'0'||ch>'9'; ch = getchar())16 if (ch=='-') f = -1;17 for (; ch>='0'&&ch<='9'; ch = getchar())18 x = x*10+ch-'0';19 return x*f;20 }21 22 bool dfs(int u) {23 for (int v=1; v<=m; ++v) {24 if (e[u][v] && !vis[v]) {25 vis[v] = true;26 if (!resut[v] || dfs(resut[v])) {27 resut[v] = u;28 return true;29 }30 }31 }32 return false;33 }34 35 void xyl() {36 int ans = 0;37 for (int i=1; i<=n; ++i) {38 memset(vis,false,sizeof(vis));39 if (dfs(i)) ans++;40 }41 printf("%d",ans);42 }43 44 int main() {45 n = read(),m = read(),E = read();46 for (int i=1; i<=E; ++i) {47 int a = read(),b = read();48 if (a >n || b > m) continue;49 e[a][b] = 1;50 }51 xyl();52 return 0;53 }
更新2018-06-03
1 #include2 #include 3 #include 4 5 const int N = 1010; 6 7 struct Edge{ 8 int to,nxt; 9 Edge() {}10 Edge(int a,int b) {to = a,nxt = b;}11 }e[1000100];12 int head[N],match[N],tot;13 bool vis[N];14 int n,m;15 16 inline int read() {17 int x = 0,f = 1;char ch = getchar();18 for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-1;19 for (; isdigit(ch); ch=getchar()) x=x*10+ch-'0';20 return x * f;21 }22 bool dfs(int u) {23 for (int i=head[u]; i; i=e[i].nxt) {24 int v = e[i].to;25 if (!vis[v]) {26 vis[v] = true;27 if (!match[v] || dfs(match[v])) {28 match[v] = u;29 return true;30 }31 }32 }33 return false;34 }35 int main () {36 n = read(),m = read();int E = read();37 for (int i=1; i<=E; ++i) {38 int u = read(),v = read();39 if (u > n || v > m) continue;40 e[++tot] = Edge(v,head[u]);41 head[u] = tot;42 }43 int ans = 0;44 for (int i=1; i<=n; ++i) {45 memset(vis,false,sizeof(vis));46 if (dfs(i)) ans++;47 }48 printf("%d",ans);49 return 0;50 }
最大流
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 const int N = 2010; 8 const int INF = 1e9; 9 struct Edge{10 int to,nxt,c;11 Edge() {}12 Edge(int x,int y,int z) {to = x,c = y,nxt = z;}13 }e[1000100];14 int q[1000100],L,R,S,T,tot = 1;15 int dis[N],cur[N],head[N];16 17 inline char nc() {18 static char buf[100000],*p1 = buf,*p2 = buf;19 return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) ? EOF :*p1++;20 }21 inline int read() {22 int x = 0,f = 1;char ch=nc();23 for (; ch<'0'||ch>'9'; ch=nc()) if(ch=='-')f=-1;24 for (; ch>='0'&&ch<='9'; ch=nc()) x=x*10+ch-'0';25 return x*f;26 }27 void add_edge(int u,int v,int c) {28 e[++tot] = Edge(v,c,head[u]);head[u] = tot;29 e[++tot] = Edge(u,0,head[v]);head[v] = tot;30 }31 bool bfs() {32 for (int i=1; i<=T; ++i) cur[i] = head[i],dis[i] = -1;33 L = 1,R = 0;34 q[++R] = S;dis[S] = 1;35 while (L <= R) {36 int u = q[L++];37 for (int i=head[u]; i; i=e[i].nxt) {38 int v = e[i].to;39 if (dis[v] == -1 && e[i].c > 0) {40 dis[v] = dis[u]+1;q[++R] = v;41 if (v==T) return true;42 }43 }44 }45 return false;46 }47 int dfs(int u,int flow) {48 if (u==T) return flow;49 int used = 0;50 for (int &i=cur[u]; i; i=e[i].nxt) {51 int v = e[i].to;52 if (dis[v] == dis[u] + 1 && e[i].c > 0) {53 int tmp = dfs(v,min(flow-used,e[i].c));54 if (tmp > 0) {55 e[i].c -= tmp;e[i^1].c += tmp;56 used += tmp;57 if (used == flow) break;58 }59 }60 }61 if (used != flow) dis[u] = -1;62 return used;63 }64 int dinic() {65 int ret = 0;66 while (bfs()) ret += dfs(S,INF);67 return ret;68 }69 int main() {70 int n = read(),m = read(),E = read();71 S = n+m+1;T = n+m+2;72 for (int i=1; i<=E; ++i) {73 int u = read(),v = read();74 if (u > n || v > m) continue;75 add_edge(u,v+n,1);76 }77 for (int i=1; i<=n; ++i) add_edge(S,i,1);78 for (int i=1; i<=m; ++i) add_edge(i+n,T,1);79 int ans = dinic();80 printf("%d",ans);81 return 0;82 }