【二分图+最小覆盖+简单题】杭电 hdu 1054 Strategic Game

 

 

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

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1054
    Name  : 1054 Strategic Game

    Date  : Monday, November 7, 2011
    Time Stage : half an hour

    Result: 
4922857	2011-11-07 20:16:34	Accepted	1054
703MS	336K	1378 B
C++	pyy


Test Data :

Review :
写完了代码，案例不通过，观摹了majia大神的代码，发现原来要构造双向图……
//----------------------------------------------------------------------------*/

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

using std::vector ;

#define MAXSIZE 1509

int		n ;
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] == -1 || find (link[j]))
			{
				link[j] = cur ;
				return 1 ;
			}
		}
	}
	return 0 ;
}

int main ()
{
	int i, j ;
	int x, id, cnt ;
	int sum ;

	while (~scanf ("%d", &n))
	{
		for (i = 0 ; i < n ; ++i)
		{
			scanf ("%d:(%d)", &id, &cnt) ;
			if (cnt)
				for (j = 0 ; j < cnt ; ++j)
				{
					scanf ("%d", &x) ;
					adj[id].push_back (x) ;
					adj[x].push_back (id) ; // 构造双向图
				}
		}

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

		printf ("%d\n", sum / 2) ;

		for (i = 0 ; i < n ; ++i)
			adj[i].clear () ;
	}
	return 0 ;
}