Machine Schedule

题目链接

题目大意

k个工作（从0开始编号），a机器n个模式（模式从0开始编号），b机器有m个模式（模式从0开始编号）；
每个工作都可以由机器a的一个模式或机器b的一个模式完成且只能由机器a的一个模式或机器b的一个模式完成；
按一定顺序安排完成工作的顺序，使得切换机器的次数最少，求最少的切换机器次数；
最开始机器a和机器b都处于0模式。

解题思路

建图：

将每个工作需要的两个种机器模式连边，那么每一条边就代表一种工作；左集合是一条边的一个端点，右集合是此边的另一个端点。
建好图了就比较好想了，要将所有工作都完成，就意味着要把所有的边全部覆盖；这就是二分图最小点覆盖问题，也就可以转化为二分图最大匹配数。

为什么这么建图？

说实话，我没想到，直接把题意理解错了。
我们可以这么试着理解：
对于一个工作，要么选a机器的模式，要么选b机器的模式，也就是说，对于一个工作而言，不可能既选a机器的模式完成的它，又选b机器的模式完成它，这样必然不是最小点覆盖。类似这种不能同时选的，我们自然想把不能同时选的放到两个不同的集合中，这就是为什么要将一个工作的a机器模式和b机器模式连边。
只要覆盖住了每条边就代表完成了全部的工作。

注意

注意“最开始机器a和机器b处于0模式”，
意味着可以通过a机器的0模式或者b机器的0模式完成的任务，可以在不切换模式的情况下完成，所以不能访问与a或b的0模式相连的边，因为不需要覆盖这条边了，这条边已经被覆盖过了。
至于“最小点覆盖=最大匹配数”的证明，读者自己百度吧，我感觉挺难的，不会。
看代码吧！

AC代码

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=110;
const int M=1005;
vector<int> e[N];
int n,m,k,cnt,vis[N],link[N],job,ma,mb;

bool dfs(int x)
{
    for(int i=0;i<e[x].size();i++)
    {
        int v=e[x][i];
        if(vis[v] || v==0) continue;//必须不能访问b机器的0模式 
        vis[v]=1;
        if(link[v]==0 || dfs(link[v]))
        {
            link[v]=x;
            return 1;
        }
    }
    return 0;
}

int main()
{
    while(~scanf("%d",&n))
    {
        if(n==0) break;
        scanf("%d%d",&m,&k);
        memset(link,0,sizeof link);
        cnt=0;
        for(int i=0;i<n;i++) e[i].clear();

        for(int i=1;i<=k;i++)
        {
            scanf("%d%d%d",&job,&ma,&mb);
            e[ma].push_back(mb);//你也可以在这里判断一下，在mb!=0的前提下push_back，这样你就不用在dfs中continue掉v==0的情况了
        }
        for(int i=1;i<n;i++)//必须是从a机器的1模式开始 
        {
            memset(vis,0,sizeof vis);
            if(dfs(i)) cnt++;
        }
        cout<<cnt<<endl;
    }
}