首页 > 代码库 > poj1325 Machine Schedule

poj1325 Machine Schedule

有nx种A类机器,有ny种B类机器,k个东西,每个东西可以在a或b启动时生产(a属于A,b属于B),初始状态AB均在0,

每次切换需要重启,要生产全部k种东西,问至少重启几次。


将每件东西a,b建边,则每条边至少需要一个点才能完成该边代表的东西,题目等价于最小点覆盖问题,既用最少的点覆盖所有的边,

根据二分图性质,最小点覆盖数=最大匹配数


#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
const int maxn=105;
using namespace std;
int e[maxn][maxn];
int vis[maxn];
int mx[maxn],my[maxn];
int nx,ny,n,k;

int path(int u)
{
    int v;
    for(v=0;v<ny;v++)
    {
        if(e[u][v]&&!vis[v])
        {
            vis[v]=1;
            if(my[v]==-1||path(my[v]))
            {
                mx[u]=v;
                my[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

int hungry()
{
    int res=0;
    memset(mx,-1,sizeof mx);
    memset(my,-1,sizeof my);
    for(int i=0;i<nx;i++)
    {
        if(mx[i]==-1)
        {
            memset(vis,0,sizeof vis);
            res+=path(i);
        }
    }
    return res;
}

int main()
{
    int a,b,c;
    while(scanf("%d",&nx)&&nx)
    {
        scanf("%d%d",&ny,&k);
        memset(e,0,sizeof e);
        while(k--)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(!b||!c) continue;//此题中 含0的不用考虑
            e[b][c]=1;
        }
        int ans=hungry();
        printf("%d\n",ans);
    }
    return 0;
}