題目大意:第一行輸入一個整數(shù)n，表示有n個節(jié)點。在接下來的n行中，每行的輸入數(shù)據(jù)的格式是:

1: (2) 4 6 :表示編號為1的人認識2個人，他們分別是4、6；

求，最多能找到多少個人，他們互不認識

解題思路:二分圖的最大獨立集。

1)最大獨立集 = ?節(jié)點數(shù) - 最大匹配數(shù)/2；

2)令女生數(shù)= 男生數(shù) = 總數(shù)

3) ??1: (2)可以采用scanf("%d: (%d)",&a,&b);來輸入

代碼如下:

?

/** 1068_1.cpp** Created on: 2013年8月30日* Author: Administrator*/ #include <iostream>using namespace std;const int maxn = 1001; int map[maxn][maxn]; int link[maxn]; bool useif[maxn]; int n;int can(int t){int i;for(i = 0 ; i < n ; ++i){if(useif[i] == 0 && map[t][i]){useif[i] = 1;if(link[i] == -1 || can(link[i])){link[i] = t;return 1;}}}return 0; }int max_match(){int i;int num = 0;memset(link,-1,sizeof(link));for(i = 0 ; i < n; ++i){memset(useif,0,sizeof(useif));if(can(i)){num++;}}return num; }int main(){while(scanf("%d",&n)!=EOF){int i,j;memset(map,0,sizeof(map));for(i = 0 ; i < n ; ++i){int a,b;scanf("%d: (%d)",&a,&b);for(j = 0 ; j < b ; ++j){int c;scanf("%d",&c);map[a][c] = 1;}}printf("%d\n",n - max_match()/2);} }

?

?

總結(jié)

以上是生活随笔為你收集整理的(step6.3.2)hdu 1068(Girls and Boys——二分图的最大独立集)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。