二分匹配1（匈牙利算法）

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　一：求最大匹配问题（匈牙利算法）

给一个二分图找一个边数最大的匹配使得任意两条选中的边均没有公共点

先贴一个匈牙利算法的模板：

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

题意：有M个女生，N个男生，他们要玩过山车又必须是一男一女一起，女生只愿意和她心中的几位男生坐在一起，问最多能匹配多少对。

 1 #include<iostream>
 2 #include<string.h>
 3 #include<vector>
 4 using namespace std;
 5 vector<int > g[1002];
 6 int mark[1002],link[1002];
 7 
 8 int dfs(int x)
 9 {
10     for(int i=0;i<g[x].size ();i++)
11     {
12         int v;
13         v=g[x][i];
14         if(mark[v]==0)
15         {
16             mark[v]=1;
17             if(link[v]==-1||dfs(link[v]))
18             {
19                 link[v]=x;
20                  return 1;              
21             }
22         }
23     }
24     return 0;
25 }
26 
27 
28 
29 int main()
30 {
31     int i,j,n,m,t,a,b,c;
32     while(scanf("%d",&t)&&t!=0)
33     {
34         scanf("%d%d",&n,&m);
35         for(i=0;i<=n;i++)
36             g[i].clear ();
37         while(t--)
38         {
39             scanf("%d%d",&a,&b);
40             g[a].push_back (b);
41         }
42         int ans=0;
43         memset(link,-1,sizeof(link));
44         for(i=1;i<=n;i++)
45         {
46             memset(mark,0,sizeof(mark));
47             ans+=dfs(i);
48         }
49         printf("%d
",ans);
50     }
51     return 0;
52 }

最大匹配变种 1：

二分图的最小顶点覆盖 ：在二分图中求最少的边让每条边至少和其中的一个点关联

hdu 1150 Machine Schedule http://acm.hdu.edu.cn/showproblem.php?pid=1150

题意：有k 个任务可以在 A 机器的某一种模式或者 B 机器上的某一种模式运行， A 机器有 n 个模式， B 机器有 m 个模式，对于每一台机器不同模式之间需要切换，问完成 k 个任务需要至少切换多少次。

最小顶点覆盖= 最大匹配数

 1 #include<iostream>
 2 #include<string.h>
 3 #include<vector>
 4 using namespace std;
 5 vector <int > g[1002];
 6 int mark[1002],link[1002];
 7 
 8 int dfs(int x)
 9 {
10     for(int i=0;i<g[x].size ();i++)
11     {
12         int v=g[x][i];
13         if(!mark[v])
14         {
15             mark[v]=1;
16             if(link[v]==-1||dfs(link[v]))
17             {
18                 link[v]=x;
19                 return 1;
20             }
21         }
22     }
23     return 0;
24 }
25 
26 int main()
27 {
28     int i,j,n,m,k,a,b,c;
29     while(scanf("%d",&n),n)
30     {
31         for(i=1;i<=n;i++)
32             g[i].clear();
33         scanf("%d%d",&m,&k);
34         for(i=0;i<k;i++)
35         {
36             scanf("%d%d%d",&c,&a,&b);
37             g[a].push_back (b);
38         }
39         int ans=0;
40         memset(link,-1,sizeof(link));
41         for(i=1;i<n;i++)
42         {
43             memset(mark,0,sizeof(mark));
44             ans+=dfs(i);
45         }
46         printf("%d
",ans);
47     }
48     return 0;
49 }
50 
51

View Code

最大匹配变种 2：

dag 图的最小路径覆盖：用尽量少的不相交的简单路径覆盖图中的所有顶点

hdu 1151 Air Raid http://acm.hdu.edu.cn/showproblem.php?pid=1151

题意：输入n,m，分别表示路口数和街道数。街道单向通行，伞兵落在某路口上，可以通过街道到达下一个路口，求至少降落几个伞兵就可访问完所有的路口

最小路径覆盖 = 顶点数 - 最大匹配数

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 
 5 int g[1002][1002],link[1002],mark[1002],n;
 6 
 7 int dfs(int x)
 8 {
 9     for(int i=1;i<=n;i++)
10     {
11         if(g[x][i]&&!mark[i])
12         {
13             mark[i]=1;
14             if(link[i]==-1||dfs(link[i]))
15             {
16                 link[i]=x;
17                 return 1;
18             }
19         }
20     }
21     return 0;
22 }
23 int main()
24 {
25     int i,j,m,t,a,b;
26     scanf("%d",&t);
27     while(t--)
28     {
29         scanf("%d%d",&n,&m);
30         memset(g,0,sizeof(g));
31         memset(link,-1,sizeof(link));
32         while(m--)
33         {
34             scanf("%d%d",&a,&b);
35             g[a][b]=1;
36         }
37         int ans=0;
38         for(i=1;i<=n;i++)
39         {
40             memset(mark,0,sizeof(mark));
41             ans+=dfs(i);
42         }
43         printf("%d
",n-ans);
44     }
45     return 0;
46 }

View Code

无向图的最小路径覆盖：

poj 3020 http://poj.org/problem?id=3020

题意：一个矩形中，有N个城市’*’，现在这n个城市都要覆盖无线，若放置一个基站，那么它至多可以覆盖相邻的两个城市。
问至少放置多少个基站才能使得所有的城市都覆盖无线？

无向二分图的最小路径覆盖 = 顶点数 – 最大二分匹配数/2 ( 因为无向图就是双向的一条边等于是两次入图正向和反向最后得到的匹配数多了一倍所以要除以2 才是原本的匹配数)

 1 #include<iostream>
 2 #include<string.h>
 3 #include<vector>
 4 using namespace std;
 5 char s[100][100];
 6 vector <int > g[1002];
 7 int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
 8 int mark[1002],link[1002],n,m,count1;
 9 
10 int ok(int x,int y)
11 {
12     if(x>=0&&x<n&&y>=0&&y<m&&s[x][y]=='*')
13         return 1;
14     return 0;
15 }
16 
17 void init()
18 {
19     int i,j;
20     for(i=0;i<n;i++)
21             for(j=0;j<m;j++)
22                 if(s[i][j]=='*')
23                 {
24                     count1++;
25                     for(int k=0;k<4;k++)
26                     {
27                         int x=i+d[k][0];int y=j+d[k][1];
28                         if(ok(x,y))
29                             g[i*m+j].push_back(x*m+y);
30                     }
31                 }
32 }
33 
34 
35 
36 int dfs(int x)
37 {
38     for(int i=0;i<g[x].size();i++)
39     {
40         int v=g[x][i];
41         if(mark[v]==0)
42         {
43             mark[v]=1;
44             if(link[v]==-1||dfs(link[v]))
45             {
46                 link[v]=x;
47                 return 1;
48             }
49         }
50     }
51         return 0;
52 }
53 
54 int main()
55 {
56     int i,j,t;
57     scanf("%d",&t);
58     while(t--)
59     {
60         scanf("%d%d",&n,&m);
61         for(i=0;i<n;i++)
62             scanf("%s",s[i]);
63         count1=0;
64         for(i=0;i<n*m;i++)
65             g[i].clear();
66         init();
67         memset(link,-1,sizeof(link));
68         int ans=0;
69         for(i=0;i<n*m;i++)
70             if(g[i].size())
71             {
72                 memset(mark,0,sizeof(mark));
73                 ans+=dfs(i);
74             }
75         printf("%d
",count1-ans+ans/2);
76     }
77     return 0;
78 }
79 
80 
81                 
82

View Code

点可以重复走的最小路径覆盖：

poj 2594 Treasure Exploration http://poj.org/problem?id=2594

【题意】：派机器人去火星寻宝，给出一个无环的有向图，机器人可以降落在任何一个点上，再沿着路去其他点探索，我们的任务是计算至少派多少机器人就可以访问到所有的点。有的点可以重复去。

【思路】：我们仍可将问题转化为最小路径覆盖。如果一个人需要经过另一个人走过的点的时候，让他直接从该点上空飞过去，越过该点，直接走下一个点。如果我们赋予每个人这种能力，那么求得的无重复点的最小路径覆盖结果，就是题目要求的结果，因为需要重复的地方只要飞过去，就可以不重复了。赋予这个能力的方法就是把所有点能间接到达的点全都改为直接到达

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 
 5 int g[1002][1002],d[1002],vis[1002],n,mark[1002],link[1002],count[1002];
 6 
 7 int dfs(int x)
 8 {
 9     for(int i=1;i<=n;i++)
10         if(mark[i]==0&&g[x][i]==1)
11         {
12             mark[i]=1;
13             if(link[i]==-1||dfs(link[i]))
14             {
15                 link[i]=x;
16                 return 1;
17             }
18         }
19         return 0;
20 }
21 
22 void floyd()
23 {
24     for(int k=1;k<=n;k++)
25         for(int i=1;i<=n;i++)
26             if(g[i][k])
27                 for(int j=1;j<=n;j++)
28                     if(g[k][j])
29                         g[i][j]=1;
30 }
31 
32 int main()
33 {
34     int i,j,m,t,a,b,ans;
35     while(scanf("%d%d",&n,&m))
36     {
37         if(n==0&&m==0)
38             break;
39         
40         memset(g,0,sizeof(g));        
41         while(m--)
42         {
43             scanf("%d%d",&a,&b);
44             g[a][b]=1;            
45         }        
46         ans=0;
47         floyd();
48         memset(link,-1,sizeof(link));
49         for(j=1;j<=n;j++)
50         {
51             memset(mark,0,sizeof(mark));
52             ans+=dfs(j);
53         }    
54         printf("%d
",n-ans);
55     }
56 return 0;
57 }

View Code

最大匹配变种 3：

二分图的最大独立集：在二分图中任意两点都不相邻的顶点的最大集合

最大独立集=结点数-最大匹配数

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

题意：n个同学，一些男女同学会有缘分成为情侣，格式ni:(m) n1 n2 n3表示同学ni有缘与n1,n2,n3成为情侣，求集合中不存在有缘成为情侣的同学的最大同学数。

 1 #include<iostream>
 2 #include<string.h>
 3 using namespace std;
 4 int mark[1002],link[1002],g[1002][1002],n;
 5 
 6 int dfs(int x)
 7 {
 8     for(int v=0;v<n;v++)
 9     {
10         if(g[x][v]&&mark[v]==0)
11         {
12             mark[v]=1;
13             if(link[v]==-1||dfs(link[v]))
14             {
15                 link[v]=x;
16                 return 1;
17                 
18             }
19         }
20     }
21     return 0;
22 }
23 
24 
25 
26 int main()
27 {
28     int i,j,m,t,ans,num;
29     char ch;
30     while(scanf("%d",&n)!=EOF)
31     {
32         memset(g,0,sizeof(g));
33         for(int m=0;m<n;m++)
34         {
35             scanf("%d%c%c%c%d%c",&i,&ch,&ch,&ch,&num,&ch);
36             while(num--)
37             {
38                 scanf("%d",&j);
39                 g[i][j]=1;
40             }
41         }
42         ans=0;
43         memset(link,-1,sizeof(link));
44         for(i=0;i<n;i++)
45             {
46                 memset(mark,0,sizeof(mark));
47                 ans+=dfs(i);
48             }
49     printf("%d
",n-ans/2);
50     }
51     return 0;
52 }

View Code

二部图的多重匹配:一般的二不图只能匹配一个点，在多重匹配图中，一个点可以匹配多给点

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

题意：世界末日即将到来，地球上有n个人想转移到m个外星球，但是不同的人适应于不同的星球(1个人可适应多个星球)，每个外星球都有人数的限制，现在给你星球人数的上限。还有每个人不同的适应情况。问，能否安排所有的人都成功地转移到外星球上

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdio.h>

 5 int mark[12],link[12][100002],g[100002][12],n,m,vis[12],num[12];
 6 
 7 int dfs(int x)
 8 {
 9     int i,j;
10     for( i=0;i<m;i++)
11     {
12         if(g[x][i]&&mark[i]==0)
13         {
14             mark[i]=1;
15             if(vis[i]<num[i])
16             {
17                 link[i][vis[i]++]=x;
18                 return 1;
19             }
20         
21                 for( j=0;j<vis[i];j++)
22                     if(dfs(link[i][j]))
23                     {
24                         link[i][j]=x;
25                         return 1;
26                     }
27         }
28     
29     }    return 0;
30 }
31 
32 
33 int main()
34 {
35     int i,j,k,a,b,c;
36     while(scanf("%d%d",&n,&m)!=EOF)
37     {
38         for(i=0;i<n;i++)
39             for(j=0;j<m;j++)
40                 scanf("%d",&g[i][j]);
41         for(i=0;i<m;i++)
42             scanf("%d",&num[i]);
43 
44         memset(link,-1,sizeof(link));
45         memset(vis,0,sizeof(vis));
46         for(i=0;i<n;i++)
47         {
48             memset(mark,0,sizeof(mark));
49             if(!dfs(i))
50                 break;            
51         }
52         if(i==n)
53             printf("YES
");
54         else
55             printf("NO
");
56     }
57     return 0;
58 }

poj 1486 Sorting Slides http://poj.org/problem?id=1486

题意：有n个大小不等透明的幻灯片（只有轮廓和上面的数字可见）A、B、C、D、E…按顺序叠放在一起，现在知道每个幻灯片大小，由于幻灯片是透明的，所以能看到幻灯片上的数字（给出了每个数字的坐标，但不知道这些数字分别属于哪个幻灯片），现在要你根据当前的已知信息，输出能够确定的幻灯片编号和数字的匹配。

先求一次最大匹配再把逐一求每一条匹配边将他们删除后最大匹配是不是还是那么大要是减少了就证明是能够确定的匹配否则不能确定

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 using namespace std;
 5 int xmin[102], xmax[102], ymin[102], ymax[102],x[102],y[102],w[102][102],mark[102],link[102],n,finalx[02],finaly[102];
 6 
 7 int ok(int j,int i)
 8 {
 9     if(x[j]>=xmin[i]&&x[j]<=xmax[i]&&y[j]>=ymin[i]&&y[j]<=ymax[i])
10         return 1;
11     return 0;
12 }
13 
14 int dfs(int x)
15 {
16     for(int i=0;i<n;i++)
17         if(!mark[i]&&w[x][i])
18         {
19             mark[i]=1;
20             if(link[i]==-1||dfs(link[i]))
21             {
22                 link[i]=x;
23                 return 1;
24             }
25         }
26         return 0;
27 }
28 
29 int solve()
30 {
31     int ans=0;
32     memset(link,-1,sizeof(link));
33     for(int i=0;i<n;i++)
34     {
35         memset(mark,0,sizeof(mark));
36         ans+=dfs(i);
37     }
38     return ans;
39 }
40 
41 int main()
42 {
43     int i,j,m,t,p=1,ans;
44     while(scanf("%d",&n),n)
45     {
46         for(i=0;i<n;i++)
47             scanf("%d%d%d%d",&xmin[i], &xmax[i], &ymin[i] ,&ymax[i]);
48         for(i=0;i<n;i++)
49             scanf("%d%d",&x[i],&y[i]);
50         memset(w,0,sizeof(w));
51         for(i=0;i<n;i++)
52             for(j=0;j<n;j++)
53                 if(ok(j,i))
54                     w[j][i]=1;
55                 ans=solve();
56                 
57             
58             
59                 int temp,flag=0;
60                 int ff[100];
61                 memset(ff,-1,sizeof(ff));
62                 for(i=0;i<n;i++)
63                     if(link[i]!=-1)
64                         ff[i]=link[i];
65                     
66                 int c=0;
67                 printf("Heap %d
",p++);
68                 for(i=0;i<n;i++)
69                 {
70                      if(ff[i]!=-1)
71                      {
72                         int xx,yy;  xx=i; yy=ff[i];
73                         w[yy][xx]=0;
74                         temp=solve();//printf("temp  %d
",temp);
75                         if(temp<ans)
76                         {
77                             flag=1;
78                             printf("(%c,%d) ",xx+'A',yy+1);
79                             
80                         }
81                         w[yy][xx]=1;
82                      }
83                     
84                 }
85                 
86             
87                 if(!flag)
88                     printf("none");
89                 printf("

");
90     }
91     return 0;
92 }

View Code

poj 2226 Muddy Fields http://poj.org/problem?id=2226

题意：有一块n*m 土地里面* 代表是泥泞的求至少要多少块长度不限宽带为1 的板子能把这些泥泞的土地都盖掉

每个点有一个x 和一个y 每个点对应一条边泥泞的全部被选中意味着每条边至少有一个结点被选中

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 using namespace std;
 5 char s[102][102];
 6 int g[1102][1102],count[1102][1102],n,m,c,maxx,link[2002],mark[2002];
 7 
 8 void build()
 9 {    
10     int i,j;
11     c=1;
12     memset(count,0,sizeof(count));
13     memset(g,0,sizeof(g));
14     for(i=0;i<n;i++)
15        for(j=0;j<m;j++)
16            if(s[i][j]=='*')
17            {
18                while(s[i][j]=='*'&&j<m)
19                    count[i][j++]=c;
20                c++;
21            }
22            maxx=c;
23            c=1;
24            for(i=0;i<m;i++)
25                for(j=0;j<n;j++)
26                    if(s[j][i]=='*')
27                    {
28                        while(s[j][i]=='*'&&j<n)
29                            if(count[j][i])
30                                g[count[j++][i]][c]=1;
31                            c++;                       
32                    }
33                    if(c>maxx)
34                        maxx=c;
35 }
36 
37 int dfs(int x)
38 {
39     for(int i=1;i<maxx;i++)
40         if(g[x][i]==1)
41         {
42             if(mark[i]==0)
43             {
44                 mark[i]=1;
45                 if(link[i]==-1||dfs(link[i]))
46                 {
47                     link[i]=x;
48                     return 1;
49                 }
50             }
51         }
52     return 0;
53 }
54 
55 int main()
56 {
57     int i,j;
58     while(scanf("%d%d",&n,&m)!=EOF)
59     {
60         for(i=0;i<n;i++)
61             scanf("%s",s[i]);
62         
63         build();
64         memset(link,-1,sizeof(link));
65         int ans=0;
66         for(i=1;i<maxx;i++)
67         {
68             memset(mark,0,sizeof(mark));
69             ans+=dfs(i);
70         }
71         printf("%d
",ans);
72 
73     }
74     return 0;
75 }

View Code

poj 2060 Taxi Cab Scheme http://poj.org/problem?id=2060

题意：出租车公司有n个任务接下来n行每行有一个时间和一个起始地点和终止地点出租车要在这个时间前来到起始点将乘客运到终点运送的时间为起始点到终点的距离求最少要多少出租车可以完成全部任务

这n个点要是 a点的时间 + 运送的时间 < b点的时间就可以把 a 和b之间连一条边

建好了图就是一个求最少路径覆盖的题目了

 1 #include<iostream>
 2 #include<string.h>
 3 #include<cstdio>
 4 #include<vector>
 5 using namespace std;
 6 struct node{int s;int x;int y;} s[1002],e[1002];
 7 vector <int > g[1002];
 8 int mark[1002],link[1002];
 9 int abs(int x,int y)
10 {
11     return x>y?x-y:y-x;
12 }
13 
14 int dfs(int x)
15 {
16     for(int i=0;i<g[x].size ();i++)
17     {
18         int v=g[x][i];
19         if(mark[v]==0)
20         {
21             mark[v]=1;
22             if(link[v]==-1||dfs(link[v]))
23             {
24                 link[v]=x;
25                 return 1;
26             }
27         }
28     }
29     return 0;
30 }
31 
32 int main()
33 {
34     int i,j,n,t,x1,y1,x2,y2,a,b,c,d,s1,s2;
35     scanf("%d",&t);
36     while(t--)
37     {
38         scanf("%d",&n);
39         for(i=0;i<2*n;i++)
40             g[i].clear();
41         for(i=0;i<n;i++)
42         {
43             scanf("%d:%d %d %d %d %d",&a,&b,&x1,&y1,&x2,&y2);
44             s1=(a)*60+b;
45             s2=s1+abs(x1-x2)+abs(y1-y2);
46             s[i].s=s1;    s[i].x=x1;  s[i].y= y1;
47             e[i].s=s2;   e[i].x=x2;  e[i].y= y2;
48         }
49         for(i=0;i<n;i++)
50             for(j=0;j<n;j++)
51                 if(i!=j)
52                 {
53                     s2=abs(e[i].x-s[j].x)+abs(e[i].y-s[j].y);
54                     if(e[i].s+s2+1<=s[j].s)
55                         g[i].push_back (j);
56                 }
57                 int ans=0;
58                 memset(link,-1,sizeof(link));
59                 for(i=0;i<n;i++)
60                 {
61                     memset(mark,0,sizeof(mark));
62                     ans+=dfs(i);
63                 }
64                 printf("%d
",n-ans);
65     }
66     return 0;
67 }

View Code