HDU 2458 最大团个数=顶点数 - 补图最大匹配数 二分匹配

题意：

给定女孩人数，男孩人数，m个边

下面m条边 u-v 表示u女孩和v男孩相互认识

男孩们都认识每个男孩，女孩们都认识每个女孩

求其中最多有多少人 两两互相认识

很显然是求最大团

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

最小覆盖数+最大独立集 = 顶点数

在二分图中 最小覆盖数 = 最大匹配数

显然这里补图一定是一个二分图

二分匹配裸题：

#include<stdio.h>#include<string.h>#define N 205int lef[N], pn, zn;//lef[v]表示Y集的点v 当前连接的点  bool T[N];     //T[u] 表示Y集 u 是否已连接X集bool map[N][N];bool match(int x){ // x和Y集 匹配 返回x点是否匹配成功for(int v=1; v <= zn; v++){if(!T[v] && map[x][v]){T[v] = true;if(lef[v] == -1 || match( lef[v] ))   //match(lef[v]) : 原本连接v的X集点 lef[v] 能不能和别人连，如果能 则v这个点就空出来和x连{lef[v] = x;return true;}}}return false;}int solve(){int ans = 0;memset(lef, -1, sizeof(lef));for(int i = 1; i<= pn; i++)//X集匹配，X集点标号从 1-pn 匹配边是G[左点].size()   {memset(T, 0, sizeof(T));if( match( i ) ) ans++;}return ans;}int main(){int Cas = 1, m, u, v;while(~scanf("%d%d%d",&pn,&zn,&m), pn+zn+m ){for(int i = 1; i <= pn; i++)for(int j = 1; j <= zn; j++)map[i][j] = true;while( m-- ){scanf("%d %d",&u,&v);map[u][v] = false;}printf("Case %d: %d\n",Cas++, pn+zn - solve());}return 0;}/*2 3 31 11 22 32 3 51 11 22 12 22 30 0 0*/