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

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

[http://acm.hdu.edu.cn/showproblem.php?pid=1150  
][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;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1150]: http://acm.hdu.edu.cn/showproblem.php?pid=1150

发表评论取消回复

表情：

评论列表（有 0 条评论，194人围观）

还没有评论，来说两句吧...

相关阅读

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

[http://acm.hdu.edu.cn/showproblem.php?pid=1150 ][http_acm.hdu.edu.cn_showproblem.php_

冷不防/ 2022年12月22日 08:40/ 0 赞/ 195 阅读

相关 poj 题目3041 Asteroids （最小点覆盖）

[http://poj.org/problem?id=3041][http_poj.org_problem_id_3041] 最小覆盖：最小覆盖要求用最少的点（Ｘ集合

不念不忘少年蓝@/ 2022年12月22日 02:25/ 0 赞/ 159 阅读

相关 HDU 1150(最小点覆盖)

题意：经典的机器调度问题。在二分图G=（X,Y;E）中求取最少的顶点集v\（在｛X,Y｝中找），使得边ei （属于E）都和至少一个顶点vi（属于v\）相关联。这就是二分图模

迷南。/ 2022年09月20日 11:21/ 0 赞/ 170 阅读

相关 Machine Schedule（最小点覆盖数）

Machine Schedule Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768

- 日理万妓/ 2022年08月01日 06:09/ 0 赞/ 153 阅读

相关 HDU3360-二分图最小点覆盖

National Treasures Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/3276

偏执的太偏执、/ 2022年07月12日 07:25/ 0 赞/ 187 阅读

相关 HDU3360-二分图最小点覆盖

National Treasures Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/3276

ゝ一世哀愁。/ 2022年07月12日 07:25/ 0 赞/ 173 阅读

相关 HDU1528-二分图最小点覆盖

Card Game Cheater Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768

我不是女神ヾ/ 2022年07月12日 07:20/ 0 赞/ 175 阅读

相关 HDU1150最小点覆盖

Machine Schedule Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768

我会带着你远行/ 2022年07月12日 05:02/ 0 赞/ 203 阅读

相关 HDU 1150 Machine Schedule（二分匹配+匈牙利算法）

As we all know, machine scheduling is a very classical problem in computer science and h

深藏阁楼爱情的钟/ 2022年06月10日 05:18/ 0 赞/ 166 阅读

相关 POJ1325 Machine Schedule（二分图最小点覆盖）

题意：有两台机器A,B及N个任务。每台机器有M种不同的模式。M,N <= 100。对每个任务i给定a\[i\]和b\[i\]，表示如果该任务在A上执行，需要设置模式为a\[i

╰半橙微兮°/ 2021年11月09日 23:44/ 0 赞/ 268 阅读