題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1068

解題思路：

這題大概意思就是說找出一個最大的集合使得該集合的任意兩個人木有關(guān)系。

根據(jù)最大獨立集?=頂點數(shù)?-?最大匹配數(shù)

由于題目沒有給出哪些是男的哪些是女的，也就是說沒有明顯的二分圖，所以將一個人拆成兩個人進行最大匹配。由于一個拆成兩個，所以最大匹配數(shù)應(yīng)該是求出來的數(shù)除以2?。最后再用頂點數(shù)減就行了。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 1005; int n,g[maxn][maxn]; int match[maxn]; bool vis[maxn];bool dfs(int u) {for(int i = 0; i < n; i++){if(vis[i] == true || g[u][i] == 0) continue;vis[i] = true;if(match[i] == -1 || dfs(match[i])){match[i] = u;return true;}}return false; }int Max_Match() {int ans = 0;memset(match,-1,sizeof(match));for(int i = 0; i < n; i++){memset(vis,false,sizeof(vis));if(dfs(i))ans++;}return ans; }int main() {int a,b,c;while(scanf("%d",&n)!=EOF){memset(g,0,sizeof(g));for(int i = 1; i <= n; i++){scanf("%d: (%d)",&a,&b);for(int j = 1; j <= b; j++){scanf("%d",&c);g[a][c] = 1;}}printf("%d\n",n - Max_Match()/2);}return 0; }

總結(jié)

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

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