hdu 题目1150 Machine Schedule（最小点覆盖）-蒲公英云

hdu 题目1150 Machine Schedule（最小点覆盖）

冷不防 2022-12-22 08:40 289阅读 0赞

http://acm.hdu.edu.cn/showproblem.php?pid=1150

没有考虑从0号开始o(╯□╰)o，但是AC了，最小点覆盖，工作看做边，A的模式为X点集合， B的模式为Y点集合，

需要用最少的点，做完所有工作（关联到所有边），即最小点覆盖

还有，题目上没说x，y的范围。（如果就是0,1,2，3，….）的话，只要判断link[y]是否为0即可，如果有的话，一开始处于0模式不用转换。。。，

/***************************
# 2013-9-3 13:34:42 
# Time: 0MS   Memory: 240K
# Author: zyh
# Status: Accepted
***************************/ 
#include<stdio.h>
#include<string.h>
#define N 105
int m,n;
bool G[N][N],vis[N];
int link[N];
bool dfs(int x){
    for(int i=1;i<=m;i++){
        if(G[x][i]&&!vis[i]){
            vis[i]=1;
            if(link[i]==-1 || dfs(link[i])){
                link[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int sum,x,y,i,k;
    while(scanf("%d",&n),n)
    {
        memset(G,0,sizeof(G));
        memset(link,-1,sizeof(link));
        scanf("%d%d",&m,&k); 
        while(k--){
            scanf("%d%d%d",&i,&x,&y);
            G[x][y]=1;
        }
        for(sum=0,i=1;i<=n;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i)) sum++;
        }
        printf("%d\n",sum);
    }
    return 0;
}