/* 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 ;
}
分享到:
相关推荐
北大POJ1163-The Triangle
北大POJ经典结题报告 北大POJ经典结题报告 北大POJ经典结题报告 注重方法,内容详尽,物超所值
很多的POJ题目答案!1000~1008,1011~1014,1016,1017,1019,1028,1032,1045,1046,1047,1050,1061,1067,1068,1088,1102,1159,1163,1183,1207,1218,1226,1247,1256,1258,1298,1316,1323,...
北大POJ3267-The Cow Lexicon
如果你为在poj上找不到解题思路而痛苦,那么这本书可以为你带来惊喜,里面包括了poj上一部分题解题报告~
ACM POJ 解题报告北大POJ 大量解题代码
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1159-Palindrome
北大POJ1837-Balance
poj 1611 The Suspects 代码 并查集的应用
北大poj JAVA源码
北大POJ1163-The Triangle 解题报告+AC代码
北大POJ第1005题答案(C语言)
北大POJ第1324题(C++)
北大POJ200多道程序解答 完整代码 供大家参考 相互切磋
poj题目分类 简单题 搜索题 模拟题 动态规划 计算几何 递推 数学题 图论 数据结构 贪心 构造 枚举 特殊问题特殊对待 博弈 适合学算法的人进行专项练习
北大POJ1080-Human Gene Functions
北大POJ初级-图算法 解题报告+AC代码