有一個集合男和一個集合女，給出兩集合間一些一一相應關系。問該兩集合中的最大獨立集的點數。

最大獨立集=頂點總數-最大匹配數

此題中。若（a，b）有關。則（b，a）有關。每個關系算了兩次，相當于二分圖的兩邊集合沒有分男女。兩邊都是總人數。

所以此題中答案應該是 頂點總數-最大匹配數/2

#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<vector> #include<queue> const int maxn=510; using namespace std;int mx[maxn],my[maxn],vis[maxn],e[maxn][maxn],n;int path(int i) {int j;for(j=0;j<n;j++){if(e[i][j]&&!vis[j]){vis[j]=1;if(my[j]==-1||path(my[j])){my[j]=i;mx[i]=j;return 1;}}}return 0; }int hungry() {int res=0;memset(mx,-1,sizeof mx);memset(my,-1,sizeof my);for(int i=0;i<n;i++){if(mx[i]==-1){memset(vis,0,sizeof vis);res+=path(i);}}return res; }int main() {int a,b,m,i;while(~scanf("%d",&n)){memset(e,0,sizeof e);for(i=0;i<n;i++){scanf("%d: (%d)",&a,&m);while(m--){scanf("%d",&b);e[a][b]=1;}}printf("%d\n",n-hungry()/2);}return 0; }

總結

以上是生活随笔為你收集整理的hdu1068 Girls and Boys --- 最大独立集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。