poj 3692Kindergarten(二分匹配模板)

题意：有n个男生和m个女生，每个男生都认识和每个女生都认识，还有k对关系中的男生和女生都认识，，老师想从中选择最大的人数并且这些人都认识

思路：显然这道题可以吧男生看为一个集合，女生为一个集合，然后可以看出，如果把每对认识的连线，然后剩下的都是不认识，那么补图明显是二分图，所以可以有最大团的知识得出

最大团=原图节点数-补图的最大二分匹配数

G的最大团指的是顶点数最多的一个团。

具体解释

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 555;int mp[N][N];int vis[N];int match[N];int n,m,k;int dfs(int u){for(int i=1;i<=m;i++){if(!mp[u][i]&&!vis[i]){vis[i]=1;if(match[i]==-1||dfs(match[i])){match[i] = u;return 1;}}}return 0;}int get_match(){int res = 0;memset(match,-1,sizeof(match));for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(dfs(i))res++;}return res;}int main(){int cas = 0;while(scanf("%d%d%d",&n,&m,&k)&&n||m||k){memset(mp,0,sizeof(mp));for(int i=0;i<k;i++){int x,y;scanf("%d%d",&x,&y);mp[x][y]=1;}printf("Case %d: %d\n",++cas,n+m-get_match());}}

谁的指间滑过了千年时光；谁在反反复复中追问可曾遗忘；

相关文章：

你感兴趣的文章：

标签云：