二分图最小点覆盖

　　二分图模型中的最小顶点覆盖问题：在二分图G=(X,Y;E)中求取最小的顶点集V* ⊂ ｛X,Y｝,使得边 e ∈ E都至少有一个顶点 v ∈ V*相关联。

　　简单地说，最小点覆盖就是从图G的顶点中取最少的点组成一个集合，使得图中所有的边都与取出来的点相连。

　　有一定理：最小顶点覆盖问题与最大匹配问题等价。

题目大意:

　　有两台机器A和B。A机器有N种不同的模式，B机器有M种不同的模式。每个任务都可以在一台机器上独立完成。如果它在机器A上运行，则机器A需要设置为模式xi；如果它在机器B上运行，则机器A需要设置为模式yi。每台机器　　　　上的任务可以按照任意顺序执行，但是每台机器每转换一次模式需要重启一次。求机器重启的最小次数。

解题思路：

　　X={机器A的集合}，Y={机器B的集合}，E={(i,j) | 任务K由机器A的i模式完成或者由机器B的j模式完成}，这样就构造了一个二分图。

　　这样构图以后，明显看出就是求最小点覆盖。

　　本题有个特殊的地方，就是0这个状态是初始状态，就是说这个状态是不需要代价的（在最小代价的情况下）。

　　求最大匹配我用的是Hopcroft-Karp算法，时间复杂度为O(m*n^1/2)。而匈牙利算法（BFS版，DFS版）时间复杂度都是O(m*n)。

下面的是代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 
 8 const int N=1005,INF=0x3f3f3f3f;
 9 int bmap[N][N],cx[N],cy[N],dx[N],dy[N];
10 bool bmask[N];
11 int nx,ny,dis,ans;
12 bool searchpath()
13 {
14     queue<int> q;
15     dis=INF;
16     memset(dx,-1,sizeof(dx));
17     memset(dy,-1,sizeof(dy));
18     for(int i=1;i<=nx;i++)
19     {
20         if(cx[i]==-1){ q.push(i); dx[i]=0; }
21         while(!q.empty())
22         {
23             int u=q.front(); q.pop();
24             if(dx[u]>dis) break;
25             for(int v=1;v<=ny;v++)
26             {
27                 if(bmap[u][v]&&dy[v]==-1)
28                 {
29                     dy[v]= dx[u] + 1;
30                     if(cy[v]==-1) dis=dy[v];
31                     else
32                     {
33                         dx[cy[v]]= dy[v]+1;
34                         q.push(cy[v]);
35                     }
36                 }
37             }
38         }
39     }
40     return dis!=INF;
41 }
42 int findpath(int u)
43 {
44     for(int v=1;v<=ny;v++)
45     {
46         if(!bmask[v]&&bmap[u][v]&&dy[v]==dx[u]+1)
47         {
48             bmask[v]=1;
49             if(cy[v]!=-1&&dy[v]==dis) continue;
50             if(cy[v]==-1||findpath(cy[v]))
51             {
52                 cy[v]=u; cx[u]=v;
53                 return 1;
54             }
55         }
56     }
57     return 0;
58 }
59 void maxmatch()
60 {
61     ans=0;
62     memset(cx,-1,sizeof(cx));
63     memset(cy,-1,sizeof(cy));
64     while(searchpath())
65     {
66         memset(bmask,0,sizeof(bmask));
67         for(int i=1;i<=nx;i++)
68             if(cx[i]==-1) ans+=findpath(i);
69     }
70 }
71 void init()
72 {
73     memset(bmap,0,sizeof(bmap));
74 }
75 int main()
76 {
77     //freopen("test.txt","r",stdin);
78     int m,i,j,k;
79     while(scanf("%d",&nx)!=EOF)
80     {
81         if(!nx) break;
82         scanf("%d%d",&ny,&m);
83         init();
84         while(m--)
85         {
86             scanf("%d%d%d",&i,&j,&k);
87             if(j&&k) bmap[j][k]=1;
88         }
89         maxmatch();
90         printf("%d
",ans);
91     }
92     return 0;
93 }

View Code