Description
有两个机器A，B。 A有n种工作模式0...n-1 B有m种工作模式0...m-1 然后又k个任务要做 每个任务可以用A机器的模式i或b机器的模式j来完成 机器开始都处于模式0 每次换模式时都要重启 问完成所有任务机器至少重启多少次
Sample Input
5 5 10//N,M,K,即A机器有5种工作模式，B有5种工作模式，共有10个任务。
0 1 1//第0个任务可用A的第1种模式和B的第1种模式完成
1 1 2//第1个任务的描述
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0
Sample Output
3
sol:把A的n种工作模式为一个顶点的集合，B的m种模式作为另一个顶点集合，对于每一个任务，要么选Ai模式，要么选Bj模式，在Ai与Bj间连边，构造二分图。
每个任务要使两台机器切换次数最少，即在二分图中，要选最少的点来覆盖所有的边，即求二分图的最小点覆盖。
代码如下：
1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 int n,m,k,ans; 5 bool vis[101]; 6 int link[101][101],mat[101]; 7 int read(){ 8 int x=0,f=1;char ch=getchar(); 9 for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1; 10 for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+ch-'0'; 11 return x*f; 12 } 13 bool hungary(int u){ 14 for(int v=0;v<m;v++) 15 if(!vis[v]&&link[u][v]){ 16 vis[v]=1; 17 if(mat[v]==-1||hungary(mat[v])){ 18 mat[v]=u;return 1;} 19 }return 0; 20 } 21 int main() 22 { 23 while(1)//读入k个任务的信息 24 { 25 n=read();if(n==0)break;//n为0结束读入 26 memset(link,0,sizeof(link)); 27 memset(mat,-1,sizeof(mat));ans=0; 28 m=read(),k=read(); 29 for(int i=1;i<=k;i++) 30 { 31 int x=read(),y=read(),z=read(); 32 if(y&&z)link[y][z]=1; 33 } 34 for(int i=0;i<n;i++) 35 { 36 memset(vis,0,sizeof(vis)); 37 if(hungary(i))ans++; 38 } 39 printf("%d ",ans); 40 } 41 return 0; 42 }