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?}

?