首页 > 代码库 > poj 1325 machine schedule

poj 1325 machine schedule

题目大意:

有两个机器,两种机器各有n,m种模式,有k个任务,每个任务可以分别由两种机器的一种模式来完成,每次切换模式都需要重启机器,问最少重启几次机器可以完成所有任务(开始两台机器都为模式0)

思路:

匈牙利最小点覆盖

因为只有两种机器,可以把每种模式都变成点,所有点只有两种颜色,就是一个二分图

然后把任务作为边,连接两种模式

然后直接上匈牙利求一下最小点覆盖ac

技术分享
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,k,a,b,c,link[210];
bool map[210][210],vis[210];
bool find(int x)
{
     for(int i=0;i<m;i++)
     {
         if(map[x][i]&&!vis[i])
         {
             vis[i]=true;
             if(link[i]==-1||find(link[i])) {link[i]=x;return true;}
         }
     }
     return false;
}
int main()
{
    while(scanf("%d",&n)&&n!=0)
    {
        scanf("%d%d",&m,&k);
        int ans=0;
        memset(link,0xff,sizeof(link));
        memset(map,false,sizeof(map));
        for(int i=0;i<k;i++) {scanf("%d%d%d",&a,&b,&c);if(b!=0&&c!=0)map[b][c]=true;}
        for(int i=0;i<n;i++)
        {
            memset(vis,false,sizeof(vis));
            if(find(i)) ans++;
        }
        printf("%d\n",ans);
    }
}
View Code

 

poj 1325 machine schedule