二分匹配

最大匹配

///1. 最大匹配数+ 最大独立集= n + m
///2: 二分图的最小点覆盖 = 最大匹配数
///3: 最小路径覆盖= 最大独立集
///最大独立集是指求一个二分图中最大的一个点集，该点集内的点互不相连。
///最小顶点覆盖是指在二分图中，用最少的点，让所有的边至少和一个点有关联。
///最小路径覆盖是指一个不含圈的有向图G 中，图中的每一个结点仅包含于P 中的一条路径中。

http://acm.hdu.edu.cn/showproblem.php?pid=2063

 1 #include<cstdio>
 2 class Bipartite_graph {  ///二分图最大匹配_匈牙利算法_O(MV^3)
 3     static const int MV=5e2+10;///点的个数max(x,y)
 4     bool mat[MV][MV],vis[MV];
 5     int res[MV],n,m,big;///res[]存y部匹配的x部的下标
 6     bool dfs(int a) {
 7         for (int i=0; i<=m; i++) {
 8             if (mat[a][i]&&!vis[i]) {
 9                 vis[i]=true;
10                 if(res[i]==-1||dfs(res[i])) {
11                     res[i]=a;
12                     return true;
13                 }
14             }
15         }
16         return false;
17     }
18 public:
19     void init(int x,int y) {///传入x部和y部点数
20         n=x;
21         m=y;
22         for(int i=0;i<=x;i++){
23             for(int j=0;j<=y;j++){
24                 mat[i][j]=false;
25                 res[j]=-1;
26             }
27         }
28     }
29     void add(int u,int v) {
30         mat[u][v]=true;
31     }
32     int solve() {
33         big=0;
34         for(int i=0; i<=n; i++) {
35             for(int j=0;j<=m;j++) vis[j]=false;
36             if(dfs(i)) big++;
37         }
38         return big;
39     }
40 } g;
41 int main(){
42     int k,n,m,x,y;
43     while(~scanf("%d",&k),k){
44         scanf("%d%d",&n,&m);
45         g.init(n,m);
46         while(k--){
47             scanf("%d%d",&x,&y);
48             g.add(x,y);
49         }
50         printf("%d
",g.solve());
51     }
52     return 0;
53 }

View Code

【HDU】
1068Girls and Boys 最大匹配★

http://acm.hdu.edu.cn/showproblem.php?pid=1068

最大独立集=n+m-最大匹配

 1 #include<cstdio>
 2 class Bipartite_graph {  ///二分图最大匹配_匈牙利算法_O(MV^3)
 3     static const int MV=2e2+10;///点的个数max(x,y)
 4     bool mat[MV][MV],vis[MV];
 5     int res[MV],n,m,big;///res[]存y部匹配的x部的下标
 6     bool dfs(int a) {
 7         for (int i=0; i<=m; i++) {
 8             if (mat[a][i]&&!vis[i]) {
 9                 vis[i]=true;
10                 if(res[i]==-1||dfs(res[i])) {
11                     res[i]=a;
12                     return true;
13                 }
14             }
15         }
16         return false;
17     }
18 public:
19     void init(int x,int y) {///传入x部和y部点数
20         n=x;
21         m=y;
22         for(int i=0;i<=x;i++){
23             for(int j=0;j<=y;j++){
24                 mat[i][j]=false;
25                 res[j]=-1;
26             }
27         }
28     }
29     void add(int u,int v) {
30         mat[u][v]=true;
31     }
32     int solve() {
33         big=0;
34         for(int i=0; i<=n; i++) {
35             for(int j=0;j<=m;j++) vis[j]=false;
36             if(dfs(i)) big++;
37         }
38         return big;
39     }
40 } g;
41 int main(){
42     int n,m,x,y;
43     while(~scanf("%d",&n)){
44         g.init(n,n);
45         for(int i=0;i<n;i++){
46             scanf("%d: (%d)",&x,&m);
47             while(m--){
48                 scanf("%d",&y);
49                 g.add(i,y);
50             }
51         }
52         printf("%d
",(n+n-g.solve())/2);
53     }
54     return 0;
55 }

View Code

1150Machine Schedule 最小点覆盖★
1151Air Raid 最小路径覆盖★
1179Ollivanders 最大匹配★
1281棋盘游戏行列匹配+求关键点★★
149850 years, 50 colors 行列匹配★
1507Uncle Tom's Inherited Land* 黑白染色+奇偶匹配(1X2的矩形覆盖)★
1528Card Game Cheater 最大匹配★
1845Jimmy’s Assignment 最大匹配(HK算法)★
2063过山车最大匹配★
2119Matrix 行列匹配
2444The Accomodation of Students 并查集分集合+最大匹配(好题!)★★
2768Cat vs. Dog 最大独立集★★
3360National Treasures 黑白染色+最小点覆盖★★
1045Fire Net 行列匹配变形★★
1350Taxi Cab Scheme 最小路径覆盖★
1960Taxi Cab Scheme 最小路径覆盖★
3118Arbiter 二分匹配本质(好题!)★★★
3729I'm Telling the Truth最大匹配+输出字典序最大的匹配情况★★
2389Rain on your Parade 最大匹配(HK算法)★★
1054Strategic Game 最小点覆盖★
2819Swap 行列匹配+输出解★★
1669 Jamie's Contact Groups 二分+多重匹配★★
3605Escape 多重匹配★
3861The King’s Problem 强连通+最小路径覆盖★★
2236无题II 二分+二分匹配★★
1083Courses 最大匹配★
1526A Plug for UNIX 最大匹配★
2458Kindergarten 行列匹配★
4160Dolls 最大匹配★
4185Oil Skimming 黑白匹配★
2413Against Mammoths 二分+二分匹配★★
3468Treasure Hunting 最短路+二分匹配★★★
3517 Adopt or not 最大独立集★★★
3026Chinese Chess 二分匹配必须边★★★
===============================================================================================
【POJ】
1087A Plug for UNIX
1274 The Perfect Stall
1469COURSES
1486 Sorting Slides 二分图的必须边
1548Robots
1698Alice's Chance
1719Shooting Contest
2060 Taxi Cab Scheme 最小路径覆盖
2112 Optimal Milking 二分+多重匹配
2226 Muddy Fields 行列的覆盖
2239 Selecting Courses
2289 Jamie's Contact Groups 二分+多重匹配
2446 Chessboard
2536 Gopher II
2584T-Shirt Gumbo
2594 Treasure Exploration 可相交最小路径覆盖
2672Hotkeys
2724 Purifying Machine
3020 Antenna Placement
3041 Asteroids 简单行列匹配
3189Steady Cow Assignment 二分+多重匹配
3216 Repairing Company
3343 Against Mammoths
3692 Kindergarten
poj2771最大独立集