学步园

啊。。这次终于挑相互认识的小盆友出去玩咧。。呵呵。。

女生之间都相互认识，男生之间也是。给你男女认识对数，求出最大数量的小盆友相互都认识。。。

类似于之前那几道，建图，只不过这次匈牙利算法算的是未标记的图，在讨论里见这个叫补图。。。

开始一直不对因为，这个矩阵不是N*N的，因为我的初始化全是0，而最后判断的也是0的点才。。。所以界限需要严格定一下。。。

最后就用总人数减去不认识的最少人数（最小顶点覆盖）即可。

#include <queue><br /> #include <stack><br /> #include <math.h><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <iostream><br /> #include <limits.h><br /> #include <string.h><br /> #include <algorithm><br /> #define MAX 202<br /> using namespace std;<br /> int map[MAX][MAX];<br /> int used[MAX];<br /> int mat[MAX];<br /> int ng,nb;<br /> int Augement(int x)<br /> {<br /> int i;<br /> for(i=1; i<=nb; i++)<br /> if( !used[i] && map[x][i] == 0 )<br /> {<br /> used[i] = 1;<br /> if( !mat[i] || Augement(mat[i]) )<br /> {<br /> mat[i] = x;<br /> return 1;<br /> }<br /> }<br /> return 0;<br /> }<br /> int Hungary()<br /> {<br /> int i,sum = 0;<br /> memset(mat,0,sizeof(mat));<br /> for(i=1; i<=ng; i++)<br /> {<br /> memset(used,0,sizeof(used));<br /> if( Augement(i) )<br /> sum++;<br /> }<br /> return sum;<br /> }<br /> int main()<br /> {<br /> int from,to,m;<br /> int ind = 1;<br /> while( ~scanf("%d%d%d",&ng,&nb,&m) )<br /> {<br /> memset(map,0,sizeof(map));<br /> if( ng == nb && ng == m && m == 0 )<br /> break;<br /> while( m-- )<br /> {<br /> scanf("%d%d",&from,&to);<br /> map[from][to] = 1;<br /> }<br /> int ans = Hungary();<br /> printf("Case %d: %d/n",ind++,ng+nb-ans);</p> <p> }<br /> return 0;<br /> }<br />