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;
}

poj1325 Machine Schedule,布布扣,bubuko.com

poj1325 Machine Schedule

原文：http://blog.csdn.net/u011032846/article/details/38012229