Poj 3692 Hdu 2458 (08 合肥Online 二分图 最大团)

个人的理解：

(1)最大团:在图中选出一些点，使得这些点两两相邻，则这些点构成的集合称作团。包含顶点数最多的团称作最大团

(2)补图:对于图G我们有相应的图G'，在G中，若没有边(u,v)，则在G'中有边(u,v)；在G中有边(u,v)则在图G'中没有边(u,v)。我们称G'为G的补图。

题意：有G个女生，B个男生，所有的女生互相认识，所有的男生互相认识，有M对男女互相认识，选出尽可能多的人数，使得两两互相认识，求这个最大的人数

#include 
#include const int N=205;
bool map[N][N],vis[N];
int match[N];
int G,B,M;bool Dfs (int u)
{for (int v=1;v<=B;v++)if (vis[v] == false && map[u][v]){vis[v]=true;if (match[v]==0 || Dfs(match[v])){match[v]=u;return true;}}return false;
}int main ()
{int num,i,x,y,T=1;while (scanf("%d%d%d",&G,&B,&M) && G*B){memset(map,true,sizeof(map));memset(match,0,sizeof(match));for (i=1;i<=M;i++){scanf("%d%d",&x,&y);map[x][y]=false;}for (num=0,i=1;i<=G;i++){memset(vis,false,sizeof(vis));if (Dfs(i))num++;}printf("Case %d: %d\n",T++,G+B-num);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！