洛谷：P3386
题目背景
二分图
题目描述
给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数
输入输出格式
输入格式：
第一行，n,m,e
第二至e+1行，每行两个正整数u,v，表示u,v有一条连边
输出格式：
共一行，二分图最大匹配
输入输出样例
输入样例#1：
|
1 2 |
1 1 1 1 1 |
输出样例#1：
|
1 |
1 |
邻接矩阵（老码风）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <cstdio> #include <iostream> #include <algorithm> #include <cstdlib> #include <cstring> using namespace std; const int maxn(1005); int ans; int n,m,e; bool vis[maxn][maxn]; bool use[maxn]; int matched[maxn]; inline bool dfs(int); int main(){ scanf("%d%d%d",&n,&m,&e); for(int i=1;i<=e;++i){ int x,y; scanf("%d%d",&x,&y); vis[x][y]=true; } for(int i=1;i<=n;++i){ memset(use,false,sizeof use); if(dfs(i)) ans++; } printf("%d\n",ans); return 0; } inline bool dfs(int x){ for(int i=1;i<=m;++i){ if(vis[x][i]&&!use[i]){ use[i]=true; if(!matched[i]||dfs(matched[i])){ matched[i]=x; return true; } } } return false; } |
邻接矩阵（新码风）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int MAXM = 1e8; const int MAXN = 1005; struct node { int to,next; }; node e[MAXM]; bool used[MAXN]; int head[MAXN],cnt,n,m,ee,Ans,Matched[MAXN]; void add(int from,int to) { e[++cnt].next = head[from]; e[cnt].to = to; head[from] = cnt; } inline bool dfs(int u) { for(int i = head[u];i;i = e[i].next) { int v = e[i].to; if(!used[v]) { used[v] = true; if(!Matched[v] || dfs(Matched[v])) { Matched[v] = u; return true; } } } return false; } int main() { cin >> n >> m >> ee; for(int i = 1;i <= ee;++i) { int from,to; cin >> from >> to; if(from > n or to > m) continue; add(from,to); } for(int i = 1;i <= n;++i) { memset(used,false,sizeof used); if(dfs(i)) Ans++; } cout << Ans << endl; return 0; } |
