題意：
? ? ?n個(gè)男孩和m個(gè)女孩，給你他們誰(shuí)和誰(shuí)彼此了解，問(wèn)你要找到一個(gè)集合，使得這個(gè)集合中的男孩和女孩相互了解，并且人數(shù)最多。


思路：

? ? ?簡(jiǎn)單題目，其實(shí)就是在求最大點(diǎn)權(quán)獨(dú)立集元素個(gè)數(shù)，先說(shuō)下點(diǎn)券獨(dú)立集的概念，就是給你一些關(guān)系，讓你找到一個(gè)最大的集合，使得集合中的任意兩個(gè)人之間都不會(huì)有關(guān)系，用的是匈牙利算法，對(duì)于這個(gè)題目我們可以吧不了解的連接到一起，這樣得到的就是集合中任意兩人都了解的最大人數(shù)了，最大點(diǎn)券獨(dú)立集元素個(gè)數(shù) = n + m - 最大匹配數(shù)。

#include<stdio.h> #include<string.h>#define N_node 200 + 10 #define N_edge 40000 + 20typedef struct {int to ,next; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int map[N_node][N_node]; int mk_dfs[N_node] ,mk_gx[N_node];void add(int a ,int b) {E[++tot].to = b;E[tot].next = list[a];list[a] = tot; }int DFS_XYL(int s) {for(int k = list[s] ;k ;k = E[k].next){int to = E[k].to;if(mk_dfs[to]) continue;mk_dfs[to] = 1;if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to])){mk_gx[to] = s;return 1;}}return 0; }int main () {int n ,m ,k ,i ,j;int a ,b ,cas = 1;while(~scanf("%d %d %d" ,&n ,&m ,&k) && n + m + k){memset(map ,0 ,sizeof(map));for(i = 1 ;i <= k ;i ++){scanf("%d %d" ,&a ,&b);map[a][b] = 1;}memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= m ;j ++)if(!map[i][j]) add(i ,j);memset(mk_gx ,255 ,sizeof(mk_gx));int sum = 0;for(i = 1 ;i <= n ;i ++){memset(mk_dfs ,0 ,sizeof(mk_dfs));sum += DFS_XYL(i);}printf("Case %d: %d\n" ,cas ++ ,m + n - sum);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ3692 最大点权独立集元素个数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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