Kindergarten

又是一道自己没思考出来的题 ！！！！！

还是老样子，题目去我拉的专题里有。

题目：

给出G给女孩，B给男孩。女孩之间是相互认识的，男孩之间也是相互认识的。现在题目中给出M对男女间会相互认识的关系普，要你计算出男女之间两两都认识的最大人数。

算法：

一开始看到以为是最大团。?。后来越想越不对啊。后来看到别人说是求解补图的问题。太深奥了。为了求出满足题目的条件，则要转换成最大独立集来求解。

证明如下：

最大独立集是所有点任意两点间都没有连边。

最大团要求：任意两点间都有连边。

补图中：任意两点间都没有连边，意味着原图中任意两点间都有连边。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; const int MAXN = 200 + 10; int G[MAXN][MAXN]; int match[MAXN]; bool used[MAXN]; int g,b,m; bool dfs(int u){ for(int i = 1;i <= b;++i){ if(!used[i]&&G[u][i]){ used[i] = 1; if(match[i] == -1||dfs(match[i])){ match[i] = u; return true; } } } return false; } void solve(){ int res = 0; memset(match,-1,sizeof(match)); for(int i = 1;i <= g;++i){ memset(used,0,sizeof(used)); if(dfs(i))res++; } printf("%d\n",g + b - res); } int main() { //freopen("Input.txt","r",stdin); int kase = 1; while(scanf("%d%d%d",&g,&b,&m),(g||m||b)){ for(int i = 0;i <= g;++i){ fill(G[i],G[i] + 1 + b,1); } int x,y; for(int i = 0;i < m;++i){ scanf("%d%d",&x,&y); G[x][y] = 0; } printf("Case %d: ",kase++); solve(); } return 0; }