首页 > 代码库 > POJ 3692 Kindergarten【最大点独立集】
POJ 3692 Kindergarten【最大点独立集】
大意:
有n个boy m个girle boy之间相互了解 girle之间相互了解
又告诉你一些boy和girle之间相互了解的关系
问最多选出多少人使其相互之间相互了解
分析:
左集合boy 右girle
若boy与girle相互不了解则建一条边,这样,有边相连的便是不相互了解的
那么最大点独立便是选取一些点使其相互之间没有边相连也就是相互了解的
note:
由于左右集合不相等所以选取nm中的较大的作为点的个数
最后结果为2 * max(n, m) - 最大匹配
代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 205; 7 8 int vis[maxn]; 9 int Link[maxn];10 int G[maxn][maxn];11 int n;12 bool Find(int i) {13 for(int j = 1; j <= n; j++) {14 if(G[i][j] == 0 && vis[j] == 0) {15 vis[j] = 1;16 if(Link[j] == -1 || Find(Link[j])) {17 Link[j] = i;18 return true;19 }20 }21 }22 return false;23 }24 25 int solve() {26 memset(Link, -1, sizeof(Link));27 int cnt = 0;28 for(int i = 1; i <= n; i++) {29 memset(vis, 0, sizeof(vis));30 if(Find(i)) cnt++;31 }32 return cnt;33 }34 35 int main() {36 int kase = 1;37 int m, k, x, y;38 while(scanf("%d %d %d",&n, &m, &k) && ( n + m + k ) ) {39 memset(G, 0, sizeof(G));40 while(k--) {41 scanf("%d %d",&x, &y);42 G[x][y] = 1;43 }44 int nn = n;45 n = max(n, m);46 printf("Case %d: %d\n",kase++, n * 2 - solve() );47 }48 return 0;49 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。