简单的二分匹配


// HDU 2063
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 using namespace std;
 7 int  k,m,n;//m :女生人数
 8 const int N=550;
 9 vector<int>v[N];
10 bool vis[N];
11 int g[N];//g[i]=j  i男  j女
12 bool match(int x){
13     for(int j=0;j<v[x].size();j++)//男生
14     {      int u=v[x][j];
15         if(!vis[u]){
16             vis[u]=1;
17             if(!g[u]||match(g[u])){
18                 //i男还没有匹配女生或者可以给该男生的原配女重新再找对应的
19                 //男生 ，那么x（女）就可以匹配i(男)了
20                 g[u]=x;
21                 return 1;
22             }    
23         }
24     }
25     return 0;
26 }
27 int  main()
28 {
29     while(~scanf("%d",&k)&&k){
30         
31         scanf("%d%d",&m,&n);
32         int x,y;
33         memset(vis,0,sizeof(vis));
34         memset(g,0,sizeof(g));//g,vis 都要清零
35         for(int  i=1;i<=m;i++)
36         {
37             v[i].clear();
38         }
39         for(int i=0;i<k;i++)
40         {
41             scanf("%d%d",&x,&y);
42             v[x].push_back(y);
43         }
44         int ans=0;
45         for(int  i=1;i<=m;i++)
46         {
47             memset(vis,0,sizeof(vis));
48             if(match(i)){
49                 ans++;
50             }
51         }
52         printf("%d
",ans);
53     }
54     return 0;
55 }
56 
57 /*
58 || 1 || 2，判断到1就知道结果肯定是真，不再继续判断，返回1。
59 || 0 || 3, 判断到第一个就知道结果是真，不再继续判断，返回1。
60 || 0 || 0;一直判断到了最后一个，才知道结果为假，返回最后一个判断的0。
61 同理：&&运算符是只要一个为假就为假，所以它会从前往后一直找假的，返回最后一个判断的值。
62 */

*/ 1 // German Collegiate Programming Contest 2015

 2 //  B. Bounty Hunter II
// n个顶点，m条边。问最少走几条路可以走完所有顶点
// （不能走走过的顶点）
/*

DAG的最小路径覆盖是指找最小数目的互相不相交的有向路径,满足DAG的所有顶点都被覆盖.

首先给出公式:DAG的最小路径覆盖数=DAG图中的节点数-相应二分图中的最大匹配数.

*/
 3 #include <iostream>
 4 #include <cstdio>
 5 #include <algorithm>
 6 #include <cstring>
 7 #include <vector>
 8 using namespace std;
 9 int  k,n;
10 const int N=2550;//要大于2000
11 vector<int>v[N];
12 bool vis[N];
13 int g[N];
14 bool match(int x){
15     for(int j=0;j<v[x].size();j++)
16     {      int u=v[x][j];
17         if(!vis[u]){
18             vis[u]=1;
19             if(g[u]==-1||match(g[u])){
20                 
21                 g[u]=x;
22                 return 1;
23             }    
24         }
25     }
26     return 0;
27 }
28 int  main()
29 {
30         scanf("%d",&n);
31         memset(g,-1,sizeof(g));
32         int x;
33         for(int i=0;i<n;i++)
34         {
35             scanf("%d",&k);
36         for(int j=0;j<k;j++)
37         {
38             scanf("%d",&x);
39             v[i].push_back(x+n);
40         }
41         }
42         int ans=0;
43         for(int  i=0;i<n;i++)
44         {
45             memset(vis,0,sizeof(vis));
46             if(match(i)){
47                 ans++;
48             }
49         }
50     
51         printf("%d
",n-ans);
52     
53     return 0;
54 }

DAG的最小路径覆盖是指找最小数目的互相不相交的有向路径,满足DAG的所有顶点都被覆盖.

首先给出公式:DAG的最小路径覆盖数=DAG图中的节点数-相应二分图中的最大匹配数.