【二分图+技巧性】北大 poj 3692 Kindergarten

 

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
	Copyright (c) 2011 panyanyany All rights reserved.

	URL   : http://poj.org/problem?id=3692
	Name  : 3692 Kindergarten

	Date  : Tuesday, November 29, 2011
	Time Stage : half and one hour

	Result: 
9610510	panyanyany
3692
Accepted	204K	141MS	C++
1429B	2011-11-29 21:15:18

Test Data :

Review :
好吧，一开始又想得很麻烦，想来想去，应该没这么麻烦的，于是参考了人家的代码……
最大独立集、补图，以前都没怎么听过，这题比较不同。具体的理念还不是很懂……
还是继续参看人家的解题报告吧……

极限定律大牛的：http://www.cppblog.com/mythit/archive/2009/06/02/86542.html
小媛的：http://blog.csdn.net/zxy_snow/article/details/6210475
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>

#define MAXKIDS		201

#define max(x, y)	(((x) > (y)) ? (x) : (y))

int		G, B, M ;
int		link[MAXKIDS] ;
bool	cover[MAXKIDS], graph[MAXKIDS][MAXKIDS] ;

bool find (int cur)
{
	int i ;
	for (i = 1 ; i <= B ; ++i)
	{
		if (cover[i] == false && graph[cur][i] == true)
		{
			cover[i] = true ;
			if (link[i] == 0 || find (link[i]))
			{
				link[i] = cur ;
				return true ;
			}
		}
	}
	return false ;
}

int main ()
{
	int i, j ;
	int x, y ;
	int sum, a, b ;
	int tcase ;

	tcase = 0 ;
	while (scanf ("%d%d%d", &G, &B, &M), G | B | M)
	{
		memset (graph, true, sizeof (graph)) ;
		for (i = 1 ; i <= M ; ++i)
		{
			scanf ("%d%d", &x, &y) ;
			graph[x][y] = false ;
		}

		sum = 0 ;
		memset (link, 0, sizeof (link)) ;
		for (i = 1 ; i <= G ; ++i)
		{
			memset (cover, 0, sizeof (cover)) ;
			sum += find (i) ;
		}

		a = max(G, B) ;
		b = G + B - sum ;
		sum = (a > b) ? a : b ;
		printf ("Case %d: %d\n", ++tcase, sum) ;
	}
	return 0 ;
}