poj 1466 Girls and Boys 二分图最大独立集（★★☆☆☆）

墨蓝 2021-12-21 13:55 221阅读 0赞

[http://poj.org/problem?id=1466][http_poj.org_problem_id_1466]

题意：从n个男女同学中找出两两没有任何关系的最大人数。

使用C++输入输出，WA了好几次，改了用C就过，也不知道怎么回事，好气愤啊！！！

Sample Input

7
    0: (3) 4 5 6
    1: (2) 4 6
    2: (0)
    3: (0)
    4: (2) 0 1
    5: (1) 0
    6: (2) 0 1
    3
    0: (2) 1 2
    1: (1) 0
    2: (1) 0

Sample Output

5
    2

Source Code

#include <iostream>
    using namespace std;
    
    const int N = 600;
    int pic[N][N],flag[N],link[N];
    
    bool find(int x){ 
    	int j;
    	for(int i=1;i<=pic[x][0];i++){ 
    		j=pic[x][i];
    		if(!flag[j]){ 
    			flag[j]=1;
    			if(link[j]==-1 || find(link[j])){ 
    				link[j]=x;
    				return true;
    			}
    		}
    	}
    	return false;
    }
    int main(){ 
    	int n,i,j,x,ans;
    	while(scanf("%d",&n)!=EOF){ 
    		memset(pic,0,sizeof pic);
    		for(i=0;i<n;i++){ 
    			link[i]=-1;
    		}
    		for(i=0;i<n;i++){ 
    			scanf("%d: ",&x);
    			scanf("(%d)",&pic[x][0]);
    			if(!pic[x][0]) continue;
    			for(j=1;j<=pic[x][0];j++){ 
    				scanf("%d",&pic[x][j]);
    			}	
    		
    		}
    		ans=0;
    		for(i=0;i<n;i++){ 
    			memset(flag,0,sizeof flag);
    			if(find(i))
    				ans++;
    		}
    		printf("%d\n",n-ans/2);
    
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/pcwl/archive/2011/04/27/2030989.html

[http_poj.org_problem_id_1466]: http://poj.org/problem?id=1466

发表评论取消回复

表情：

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

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

相关阅读

相关 BOJ 5291 Girls and Boys //二分图水题

Girls and Boys Time Limit: 10000ms Memory Limit: 32768KB This problem will be judge

ゝ一世哀愁。/ 2022年08月10日 14:45/ 0 赞/ 158 阅读

相关 Girls and Boys（最大独立集问题）

Girls and Boys Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768

￡神魔★判官ぃ/ 2022年08月01日 06:09/ 0 赞/ 161 阅读

相关 HDU2768-二分图最大独立集

Cat vs. Dog Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Ja

你的名字/ 2022年07月12日 07:24/ 0 赞/ 162 阅读

相关 HDU2768-二分图最大独立集

Cat vs. Dog Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Ja

柔光的暖阳◎/ 2022年07月12日 07:24/ 0 赞/ 153 阅读

相关 HDU 1068 Girls and Boys（二分图匹配+最大独立集+匈牙利算法）

the second year of the university somebody started a study on the romantic relations bet

矫情吗；*/ 2022年06月10日 08:46/ 0 赞/ 126 阅读

相关 Girls and Boys【二分匹配之最大独立集】

Girls and Boys > the second year of the university somebody started a study on the ro

谁借莪１个温暖的怀抱￠/ 2022年05月31日 01:20/ 0 赞/ 134 阅读

相关 HDU - 1068 Girls and Boys（二分匹配）

Girls and Boys Problem Description the sec

淩亂°似流年/ 2022年05月17日 12:04/ 0 赞/ 173 阅读

相关 POJ 1466 Girls and Boys 题解《挑战程序设计竞赛》

[为什么80%的码农都做不了架构师？>>> ][80_] ![hot3.png][] ![POJ 1466 Girls and Boys 题解《挑战程序设计竞赛》][PO

Bertha 。/ 2022年01月15日 10:39/ 0 赞/ 230 阅读

相关 poj 1466 Girls and Boys 二分图最大独立集（★★☆☆☆）

[http://poj.org/problem?id=1466][http_poj.org_problem_id_1466] 题意：从n个男女同学中找出两两没有任何关系的最大

墨蓝/ 2021年12月21日 13:55/ 0 赞/ 222 阅读

相关 ZOJ—— 1137 Girls and Boys（二分匹配）

题目链接：[http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1137][http_acm.zju.ed

小鱼儿/ 2021年09月26日 12:28/ 0 赞/ 252 阅读