首页 > 代码库 > POJ 3692 Kindergarten【最大点独立集】

POJ 3692 Kindergarten【最大点独立集】

2024-07-18 12:51:58   220人阅读

大意：

有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 }
View Code

 


联系
我们