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

傷城~ 2022-08-24 11:28 155阅读 0赞

个人的理解：

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

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

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

#include <cstdio>
    #include <cstring>
    
    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;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，155人围观）

还没有评论，来说两句吧...

相关阅读

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

个人的理解： (1)最大团:在图中选出一些点，使得这些点两两相邻，则这些点构成的集合称作团。包含顶点数最多的团称作最大团 (2)补图:对于图G我们有相应的图G'，在G中，若

傷城~/ 2022年08月24日 11:28/ 0 赞/ 156 阅读

相关 hdu 2444 二分图判定+求二分图最大匹配

The Accomodation of Students Time Limit: 5000/1000 MS (Java/Others) Memory Limit:

分手后的思念是犯贱/ 2022年08月02日 13:36/ 0 赞/ 233 阅读

相关 hdu 1045 二分图最大匹配

建图的过程当时不会，参考了别人的代码 //hdu 1045 include<map> include<vector> include<c

深碍√TFBOYSˉ_/ 2022年08月02日 12:47/ 0 赞/ 216 阅读

相关 HDU1179-二分图最大匹配

Ollivanders: Makers of Fine Wands since 382 BC. Time Limit: 2000/1000 MS (Java/O

朱雀/ 2022年07月12日 05:03/ 0 赞/ 222 阅读

相关 HDU3585-二分+最大团

maximum shortest distance Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 327

秒速五厘米/ 2022年07月10日 11:58/ 0 赞/ 143 阅读

相关 POJ 3692 Kindergarten（最大匹配+匈牙利算法+补图思想）

In a kindergarten, there are a lot of kids. All girls of the kids know each other and al

青旅半醒/ 2022年06月10日 04:12/ 0 赞/ 128 阅读

相关 POJ 1469 COURSES 二分图最大匹配

Description Consider a group of N students and P courses. Each student visits zero, one

悠悠/ 2022年05月27日 01:22/ 0 赞/ 159 阅读

相关 POJ - 3692 Kindergarten（二分匹配）

Kindergarten Description In a kindergart

曾经终败给现在/ 2022年05月17日 12:37/ 0 赞/ 132 阅读

相关 HDU 6350 Always Online (仙人掌图，最大流)

[传送门][Link 1] 这道题真的是坑，竟然用ull，ll都会爆。首先这是一个仙人掌图。题意让求任意两点最大流，再进行异或。先说最大流，对于环上任意两点最大流，就是两

ゝ一纸荒年。/ 2022年05月15日 22:16/ 0 赞/ 172 阅读

相关 hdu 1281 二分图最大匹配

对N个可以放棋子的点(X1,Y1),(x2,Y2)......(Xn,Yn);我们把它竖着排看看~（当然X1可以对多个点~） X1 Y1 X2 Y2 X3 Y3 ...

落日映苍穹つ/ 2022年03月30日 07:38/ 0 赞/ 435 阅读