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

本文主要是介绍hdu 题目1150 Machine Schedule（最小点覆盖），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

这篇关于hdu 题目1150 Machine Schedule（最小点覆盖）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---