hdu 1150 Machine Schedule 最小覆盖点集

题意：x,y两台机器各在一边，分别有模式x0 x1 x2 ... xn， y0 y1 y2 ... ym，

现在对给定K个任务，每个任务可以用xi模式或者yj模式完成，同时变换一次模式需要重新启动一次机器，问最少的启动次数
链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1150
思路：
稳定转化成给定k条边，使得每一条边最少被一个点覆盖，即最小覆盖点集
最后求出的最大匹配数需要减一才是启动次数，注意到刚开始两台机器都是在0模式下，所以没有0模式，最后就不需要减一
代码：

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 int m,n,sum;
 5 int g[105][105],vis[105],who[105];
 6 bool find(int x) {
 7     for(int i=0; i<m; ++i) {
 8         if(g[x][i]&&!vis[i]) {
 9             vis[i]=1;
10             if(who[i]==-1||find(who[i])) {
11                 who[i]=x;
12                 return true;
13             }
14         }
15     }
16     return false;
17 }
18 int main() {
19     //freopen("in.txt","r",stdin);
20     //freopen("out.txt","w",stdout);
21     ios::sync_with_stdio(false);
22     int k,u,v;
23     while(cin>>n&&n) {
24         cin>>m>>k;
25         memset(g,0,sizeof(g));
26         memset(who,-1,sizeof(who));
27         int temp,flag=0;
28         while(k--) {
29             cin>>temp>>u>>v;
30             if(!u||!v) flag=1;
31             g[u][v]=1;
32         }
33         sum=0;
34         for(int i=0; i<n; ++i) {
35             memset(vis,0,sizeof(vis));
36             if(find(i)) sum++;
37         }
38         if(flag) sum--;
39         cout<<sum<<endl;
40     }
41     return 0;
42 }

View Code