首页 > 代码库 > 最大团=补图的最大独立集

最大团=补图的最大独立集

2024-07-26 18:36:27   222人阅读

hdu2458

题意：给定G(G <= 200)个女孩和B(B <= 200)个男孩，以及M(0 <= M <= G*B)条记录(x, y)表示x号女孩和y号男孩互相认识。并且所有的女孩互相认识，所有的男孩互相认识，求找到最大的一个集合使得所有人都认识。

即求图的最大完全子图（最大团），那么可以转化为求补图的最大独立集（集合中的任意两点没有边相邻），而补图正好是一个二分图，二分图的最大独立集 = 顶点数 - 最大匹配

 1 //求最大独立集 2 #include <stdio.h> 3 #include <string.h> 4 const int N = 222; 5 int G,B,m; 6 int Map[N][N]; 7 bool vis[N]; 8 int cx[N],cy[N]; 9 10 bool dfs(int u)11 {12     int i;13     for(i=1; i<=B; ++i)14     {15         if(!vis[i] && Map[u][i])16         {17             vis[i] = true;18             if(cy[i] == -1 || dfs(cy[i]))19             {20                 cy[i] = u;21                 cx[u] = i;22                 return true;23             }24         }25     }26     return false;27 }28 int MaxMatch()29 {30     memset(cx, -1, sizeof(cx));31     memset(cy, -1, sizeof(cy));32     int ans = 0;33     for(int i=1; i<=G; ++i)34     {35         if(cx[i] == -1)36         {37             memset(vis, 0, sizeof(vis));38             ans += dfs(i);39         }40     }41     return ans;42 }43 int main()44 {45     int a,b,i;46     int tCase = 1;47     while(true)48     {49         scanf("%d%d%d",&G,&B,&m);50         if(!G && !B && !m)51             break;52         memset(Map, 0, sizeof(Map));53         for(i=1; i<=m; ++i)54         {55             scanf("%d%d",&a,&b);56             Map[a][b] = 1;    57         }58         for(i=1; i<=G; ++i)59             for(int j=1; j<=B; ++j)60                 Map[i][j] = !Map[i][j];61         int ans = MaxMatch();62         printf("Case %d: %d\n",tCase++,G + B - ans);63     }64 }

 

最大团=补图的最大独立集


联系
我们