POJ 1325 Machine Schedule（最小点覆盖）

题意：

两种机器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;
}

秒客网

POJ 1325 Machine Schedule（最小点覆盖）

相关文章