弱菜需要更加多的学习！！

英文题还是给出题意吧，英文太头疼了。。。

 

题意： A机器n种工作模式，B机器m种工作模式，共有k个任务。

（i,x,y）代表：任务i可由A机器x模式或者B机器y模式完成。

任务顺序可以随便改动，如果A或者B机器需要更换模式，则需要重启机器。

求完成工作，需要最少启动机器次数。

 

解题思路： 画出二分图，易知该问题为最小点覆盖问题，根据König定理：最小顶点覆盖 = 最大匹配数  

给出大牛的证明：

最小点覆盖定义：假如选了一个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边。

算了，还是给链接吧- -。。。：

 

我的代码：

#include
    
     #include
     
      using namespace std;int map[111][111];int tmp[111];bool flag[111];int n,m;int DFS(int x){    for(int i=1;i<=m;i++)       //机器B集合    {        if(map[x][i]&&!flag[i])        //未被匹配        {            flag[i]=true;            if(tmp[i]==-1||DFS(tmp[i]))            {                tmp[i]=x;                return 1;            }        }    }    return 0;}int main(){    int k,t,x,sum,y;    while(cin>>n&&n!=0)    {        cin>>m>>k;        memset(map,0,sizeof(map));        for(int i=0;i
      
       >t;            cin>>x>>y;            map[x][y]=1;        }        //求最大匹配        memset(tmp,-1,sizeof(tmp));        sum=0;        for(int i=1;i<=n;i++)           //匹配a机器        {            memset(flag,0,sizeof(flag));            sum+=DFS(i);        }        cout<
       
        <