POJ 1325 Machine Schedule(二分图最小点集覆盖)

 

题目链接：http://poj.org/problem?id=1325 

 

题意：A机器有n个模式，B机器有m个模式，有k个任务，第i个任务可以用A机器的ai模式或者B机器的bi模式，换模式需要重启，开始两个机器都在模式0，问最少需要重启几次。

分析： 要求最小的重启次数，也就是求出除了0模式，最少要工作在几个模式

建图：A的模式为X集，B的模式为Y集，每个任务看做一条线，连接X集和Y集，则问题转化为求X、Y中最少的点，使得每条线至少有一个端点被选。即最小点集覆盖。

根据最小点集覆盖=二分图最大匹配。

 

代码：

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4  using  namespace std;
 5  const  int N= 1001;
 6  int map[N][N],vis[N],link[N];
 7  int n1,n2,k;
 8  int find( int x)
 9 {
10      int i;
11      for(i= 1;i<=n2;i++)
12     {
13          if(map[x][i]&&!vis[i])
14         {
15             vis[i]= 1;
16              if(!link[i]||find(link[i]))
17             {
18                 link[i]=x;
19                  return  1;
20             }
21         }
22     }
23      return  0;
24 }
25  int main()
26 {
27      int a,b,c,i,sum;
28      while(~scanf( " %d ",&n1))
29     {
30          if(!n1)
31              break;
32         scanf( " %d%d ",&n2,&k);
33         sum= 0;
34         memset(map, 0, sizeof(map));
35         memset(link, 0, sizeof(link));
36          while(k--)
37         {
38             scanf( " %d%d%d ",&a,&b,&c);
39              if(b*c)
40                 map[b][c]= 1;
41         }
42          for(i= 1;i<=n1;i++)
43         {
44             memset(vis, 0, sizeof(vis));
45              if(find(i))
46                 sum++;
47         }
48         printf( " %d\n ",sum);
49     }
50      return  0;
51 }