POJ 1325 Machine Schedule(最小点覆盖)

时间:2021-03-11 05:52:42

http://poj.org/problem?id=1325

题意:

两种机器A和B.机器A具有n种工作模式,称为mode_0,mode_1,...,mode_n-1,同样机器B有m种工作模式mode_0,mode_1,..., mode_m-1。开始时,它们都在mode_0工作。 

对于给定的k个作业,可以在特定模式下的两个机器中的任一个中处理它们中的每一个。例如,作业0可以在机器A在mode_3处理,或者在机器B在mode_4处理,作业1可以在机器A中在mode_2处理,或者在机器B中在mode_4处理, 等等。因此,对于作业i,约束可以表示为三元组(i,x,y),这意味着它可以在mode_x的机器A中或者在mode_y的机器B中被处理。

显然,为了完成所有的工作,我们需要不时地改变机器的工作模式,但不幸的是,机器的工作模式只能通过手动重新启动来改变。通过更改作业的顺序并将每个作业分配给合适的机器,请编写程序以最小化重新启动机器的时间。 机器的工作模式只能通过手动重新启动来更改。通过更改作业的顺序并将每个作业分配给合适的机器,请编写程序以最小化重新启动机器的时间。机器的工作模式只能通过手动重新启动来更改。通过更改作业的顺序并将每个作业分配给合适的机器,请编写程序以最小化重新启动机器的时间。

 

思路:

建一个二分图,左边为A机器,右边为B机器,把每个作业可选的两个模式连一条边,这道题就是最小点覆盖问题,用最少的点去覆盖所有边。

最小点覆盖=最大匹配。

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

int g[105][105];
int vis[105];
int match[105];
int n, m, k;

int dfs(int x)
{
    for (int i = 0; i < m; i++)
    {
        if (g[x][i] && !vis[i])
        {
            vis[i] = 1;
            if (match[i]==-1 || dfs(match[i]))
            {
                match[i] = x;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    //freopen("D:\\txt.txt", "r", stdin);
    int id, a, b;
    while (~scanf("%d",&n))
    {
        if (n == 0)  break;
        scanf("%d%d", &m, &k);
        memset(g, 0, sizeof(g));
        memset(match, -1, sizeof(match));
        for (int i = 0; i < k; i++)
        {
            scanf("%d%d%d", &id, &a, &b);
            if (a!=0 && b!=0)
            {
                g[a][b] = 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            memset(vis, 0, sizeof(vis));
            if (dfs(i)) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}