【最大流】北大 poj 1274 The Perfect Stall

 

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

	URL   : http://poj.org/problem?id=1274
	Name  : 1274 The Perfect Stall

	Date  : Sunday, January 1, 2012
	Time Stage : one hour

	Result: 
9696355	panyanyany
1274
Accepted	824K	266MS	C++
1965B	2012-01-01 17:35:47

Test Data :

Review :
哦，二分图用网络流来做，就是一个多源多汇点的问题了。不过很显然可以
把它转化为单源单汇点问题，那就是以 1~n 为奶牛编号，n+1 ~ n+m 为畜栏
编号，添加一个 0 为源点编号，n+m+1 为汇点编号。则此网络流形式为：
源点同时与 n 条奶牛相连，奶牛再与畜栏相连，m 个畜栏同时与汇点相连。
每条连线的流量设为 1，则源点到汇点的最大流即相当于最大匹配。从而得到解。

套模板的题目，很容易过～
//----------------------------------------------------------------------------*/

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

using namespace std ;

#define DEBUG

#define min(x, y)	((x) < (y) ? (x) : (y))

#define INF		0x3f3f3f3f
#define MAXN	202*2

int		n, m ;
int		map[MAXN][MAXN], path[MAXN], flow[MAXN] ;

int Mark_Points (const int start, const int end)
{
	int			i, t ;
	queue<int>	q ;

	memset (path, -1, sizeof (path)) ;
	flow[start] = INF ;
	q.push (start) ;

	while (!q.empty ())
	{
		t = q.front () ;
		q.pop () ;

		if (end == t)
			break ;

		for (i = 0 ; i <= end ; ++i)
		{
			if (i != start && map[t][i] && path[i] == -1)
			{
				path[i] = t ;
				flow[i] = min (flow[t], map[t][i]) ;
				q.push (i) ;
			}
		}
	}

	if (path[end] == -1)
		return -1 ;

	return flow[end] ;
}

int Edmonds_Kard (const int start, const int end)
{
	int		incr, step, curr, prev ;

	incr = 0 ;
	while ((step = Mark_Points (start, end)) != -1)
	{
		incr += step ;
		
		curr = end ;
		while (curr != start)
		{
			prev = path[curr] ;
			map[prev][curr] -= step ;
			map[curr][prev] += step ;
			curr = prev ;
		}
	}
	return incr ;
}

int main (void)
{
	int		i, j ;
	int		num, stall ;
	while (~scanf ("%d%d", &n, &m))
	{
		memset (map, 0, sizeof (map)) ;
		for (i = 1 ; i <= n ; ++i)
		{
			map[0][i] = 1 ;			// 源点到各奶牛的流量
			scanf ("%d", &map[i][0]) ;
			for (j = 1 ; j <= map[i][0] ; ++j)
			{
				scanf ("%d", &stall) ;
				map[i][stall+n] = 1 ;	// 奶牛到对应畜栏的流量
			}
		}
		for (i = 1 ; i <= m ; ++i)
			map[i+n][m+n+1] = 1 ;		// 各畜栏到汇点的流量

		printf ("%d\n", Edmonds_Kard (0, m+n+1)) ;
	}
	return 0 ;
}