【最大流】北大 poj 1273 Drainage Ditches

 

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

	URL   : http://poj.org/problem?id=1273
	Name  : 1273 Drainage Ditches

	Date  : Sunday, January 1, 2012
	Time Stage : seven to eight hours around

	Result: 
9696192	panyanyany
1273
Accepted	348K	16MS	C++
1974B	2012-01-01 15:55:41
9696127	panyanyany
1273
Wrong Answer			C++
2316B	2012-01-01 15:03:34
9696116	panyanyany
1273
Wrong Answer			C++
2319B	2012-01-01 14:55:28

Test Data :

Review :
最大流，看了许久，大部分都可以慢慢看懂，唯一难搞的就是增加反向边的问题，
看到大牛的例子，才明白反向边确实很重要。
一开始看的是这位大牛的文章：
http://www.cppblog.com/mythit/archive/2009/04/19/80470.aspx
这篇文章则给出了例子，证明反向边确实重要：
http://pictureyong.blog.163.com/blog/static/851870682011299044852/
这位大牛的解释挺详细的：
http://blog.csdn.net/akof1314/article/details/4845183

听华神说这种方法是最慢的，当时有脑没脑地想了一下，跟深搜比起来，广搜应该是很快的了。
后来突然意识到，这种算法不止搜了一次！也就是说，如果一张图很大的话，这种算法可能会
需要对其反复搜索，而每次大范围的搜索却又只找到一条路，如果路不对，还要继续找……于是
这样就会很费时间了……呃，好吧，我也是刚学，进阶的事慢慢来……
//----------------------------------------------------------------------------*/

#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

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

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

	memset (path, 0, sizeof (path)) ;

	flow[start] = INF ;
	q.push (start) ;
	
//	puts ("---------------------Loop:") ;
	while (!q.empty ())
	{
		t = q.front () ;
		q.pop () ;

		if (end == t)
			break ;

//		printf ("Point: %d\n", t) ;
		for (i = 1 ; i <= end ; ++i)
		{
			if ((i != start) && map[t][i] && !path[i])
			{
				path[i] = t ;
				flow[i] = min (flow[t], map[t][i]) ;
//				printf ("\tPoint: %d, (%d, %d)\n", i, path[i], flow[i]) ;
				q.push (i) ;
			}
		}
	}
	if (path[end] == 0)
		return -1 ;
	return flow[end] ;
}

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

	incr = 0 ;
	while ((step = Mark_Point (start, end)) != -1)
	{
		incr += step ;
		curr = end ;

		while (curr != start)
		{
			prev = path[curr] ;
			map[prev][curr] -= step ;
			map[curr][prev] += step ;
//			printf ("Point: %d --> Point: %d === %d\n", prev, curr, 
//				map[prev][curr]) ;
			curr = prev ;
		}
	}
	return incr ;
}

int main (void)
{
	int	i, j ;
	int x, y, c ;
	while (~scanf ("%d%d", &n, &m))
	{
		memset (map, 0, sizeof (map)) ;
		for (i = 0 ; i < n ; ++i)
		{
			scanf ("%d%d%d", &x, &y, &c) ;
			map[x][y] += c ;
		}

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