獨立集：任意兩點都不相連的頂點的集合
獨立數：獨立集中頂點的個數
完全子圖：任意兩點都相連的頂點的集合
最大完全數：最大完全子圖中頂點的個數
最大完全數=原圖的補圖的最大獨立數
最大獨立數=頂點數-最大匹配數
這樣，就可以求出最大完全數
PKU 3692
1 #include<iostream>
2#include<algorithm>
3using namespace std;
4#define maxn 210
5#define max(x,y) ((x)>(y)?(x):(y))
6bool map[maxn][maxn],mark[maxn] ;
7int nx,ny,cx[maxn],cy[maxn];
8int path(int u)
9   {
10 for (int v = 1;v <= ny; v++)
11 if (map[u][v] && !mark[v])
12  {
13 mark[v] = 1 ;
14 if (cy[v] == -1 || path(cy[v]))
15 {
16 cx[u] = v ;
17 cy[v] = u ;
18 return 1 ;
19 }
20 }
21 return 0 ;
22 }
23int MaxMatch()
24{
25 int res=0 ;
26 memset(cx , 0xff , sizeof(cx)) ;
27 memset(cy , 0xff , sizeof(cy)) ;
28 for (int i = 1 ; i <= nx ; i++)
29 if (cx[i] == -1)
30 {
31 memset(mark , 0 , sizeof(mark)) ;
32 res += path(i) ;
33 }
34 return res ;
35}
36int main()
37{
38 int g,b,m,x,y,k;
39 k=1;
40 while(scanf("%d%d%d",&g,&b,&m)!=EOF)
41 {
42 if(g==0&&b==0&&m==0)
43 break;
44 nx=g,ny=b;
45 for(int i=1;i<=g;i++)
46 for(int j=1;j<=b;j++)
47 map[i][j]=1;
48 while(m--)
49 {
50 scanf("%d%d",&x,&y);
51 map[x][y]=0;
52 }
53 printf("Case %d: %d\n",k++,g+b-MaxMatch());
54 }
55}
|