POJ1325 Machine Schedule【二分图最小点覆盖】

题目链接:

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


题目大意:

有两台机器A和B,机器A有N种不同的模式,编号为0~N-1。机器B有M种不同的模式,编号为0~M-1。

在一开始的时候,机器A和B都处于0模式。现在需要用两台机器来处理K项任务,任务编号为0~K-1。每

一项任务都可以在A或B的指定状态下完成。例如任务1可以在机器A的2模式下完成,也可以在机器B的4

模式下完成。对于第i想任务用(i,x,y)来表示第i项任务可以在机器A的x模式下或机器B的y模式下完成。

为了完成所有任务,不得一次次地切换机器的工作模式。而切换机器的工作模式只能通过重启机器来完

成。那么问题来了:最少需要重启多少次机器,能够完成这K项任务。


思路:

建立一个二分图,一边为机器A,另一边为机器B。一项任务既能在机器A的x模式或是机器B的y模式下完

成,则在二分图中建立一条边(x,y)。求最少的机器切换次数,就是求是否存在一个最小规模的点集,使

得所有的边都至少和这个点集中的一个点相关联,也就是求二分图最小点集覆盖。而二分图最小点覆盖等

于二分图最大匹配,直接用匈牙利算法就可以求出了。


AC代码:

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

const int MAXN = 110;

bool Map[MAXN][MAXN],Mask[MAXN];

int NX,NY;
int cx[MAXN],cy[MAXN];

int FindPath(int u)
{
    for(int i = 0; i < NY; ++i)
    {
        if(Map[u][i] && !Mask[i])
        {
            Mask[i] = 1;
            if(cy[i] == -1 || FindPath(cy[i]))
            {
                cy[i] = u;
                cx[u] = i;
                return 1;
            }
        }
    }
    return 0;
}

int MaxMatch()
{
    for(int i = 0; i < NX; ++i)
        cx[i] = -1;
    for(int i = 0; i < NY; ++i)
        cy[i] = -1;

    int res = 0;
    for(int i = 0; i < NX; ++i)
    {
        if(cx[i] == -1)
        {
            for(int j = 0; j < NY; ++j)
                Mask[j] = 0;
            res += FindPath(i);
        }
    }
    return res;
}

int main()
{
    int N,M,K,a,u,v;
    while(~scanf("%d",&N) && N)
    {
        memset(Map,0,sizeof(Map));
        scanf("%d%d",&M,&K);
        NX = N,NY = M;
        for(int i = 1; i <= K; ++i)
        {
            scanf("%d%d%d",&a,&u,&v);
            if(u*v != 0)
                Map[u][v] = 1;
        }
        printf("%d\n",MaxMatch());
    }

    return 0;
}


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。