【二分图+最大匹配】北大 poj 3041 Asteroids

 

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

	URL   : http://poj.org/problem?id=3041
	Name  : 3041 Asteroids

	Date  : Saturday, November 19, 2011
	Time Stage : one hour

	Result: 
9578655	panyanyany
3041
Accepted	224K	32MS	C++
1259B	2011-11-19 21:21:01
9578476	panyanyany
3041
Accepted	264K	16MS	C++
1304B	2011-11-19 20:46:42
9578453	panyanyany
3041
Wrong Answer			C++
1310B	2011-11-19 20:42:34

Test Data :

Review :
一开始觉得是最小顶点覆盖，结果错了，看人家的钥匙报告，才知道原来是
最大匹配……囧……
//----------------------------------------------------------------------------*/

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

using std::vector ;

#define MAXSIZE		508

int		n, k ;
int		link[MAXSIZE], cover[MAXSIZE] ;

vector<int> adj[MAXSIZE] ;

int find (int cur)
{
	int i, j ;
	for (i = 0 ; i < adj[cur].size () ; ++i)
	{
		j = adj[cur][i] ;
		if (cover[j] == false)
		{
			cover[j] = true ;
			if (link[j] == false || find (link[j]))
			{
				link[j] = cur ;
				return 1 ;
			}
		}
	}
	return 0 ;
}

int main ()
{
	int i, j ;
	int r, c ;
	int sum ;

	while (~scanf ("%d%d", &n, &k))
	{
		for (i = 1 ; i <= n ; ++i)
			adj[i].clear () ;

		for (i = 1 ; i <= k ; ++i)
		{
			scanf ("%d%d", &r, &c) ;
			adj[r].push_back (c) ;
		}

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

		// 感觉应该是最小顶点覆盖，怎么会是最大匹配呢？
		printf ("%d\n", sum) ;
	}
	return 0 ;
}