【最大流+dinic+二分】北大 poj 2455 Secret Milking Machine_C/C++_编程开发_程序员俱乐部

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

    URL   : http://poj.org/problem?id=2455
    Name  : 2455 Secret Milking Machine

    Date  : Sunday, February 12, 2012
    Time Stage : 4 hours

    Result:
9799773	panyanyany
2455
Accepted	1900K	282MS	C++
3943B	2012-02-12 21:46:03

Test Data :
7 9 2
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3


Review :
TLE 4个小时，原来是模板有问题，好多细节理解不到位啊！
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>


#define MEM(a, v)		memset (a, v, sizeof (a))	// a for address, v for value
#define max(x, y)		((x) > (y) ? (x) : (y))
#define min(x, y)		((x) < (y) ? (x) : (y))

#define INF		(0x3f3f3f3f)
#define MAXN	(204)

#define DB	/##/

struct EDGE {
	int u, v, c, n ;
};

int		n, p, t, eCnt ;
int		level[MAXN], q[MAXN], vertex[MAXN] ;
EDGE	net[MAXN*MAXN*10] ;

struct E {
	int u, v, c ;
} ed[MAXN*MAXN*10] ;

inline void init()
{
//	MEM (map, INF) ;
}

inline void insert (int u, int v, int c)
{
	net[eCnt].u = u ;
	net[eCnt].v = v ;
	net[eCnt].c = c ;
	net[eCnt].n = vertex[u] ;
	vertex[u] = eCnt++ ;

	net[eCnt].u = v ;
	net[eCnt].v = u ;
	net[eCnt].c = c ;
	net[eCnt].n = vertex[v] ;
	vertex[v] = eCnt++ ;
}

void makegraph (int lim)
{
	int i ;
	MEM(vertex, -1) ;
	eCnt = 0 ;
	for (i = 1 ; i <= p ; ++i)
		if (ed[i].c <= lim)
			insert (ed[i].u, ed[i].v, 1) ;
}

void out ()
{
	int i, j ;
	for (i = 1 ; i <= n ; ++i)
	{
		for (j = 1 ; j <= n ; ++j)
			printf ("%d ", net[i].c) ;
		puts ("") ;
	}
}

int dinic (const int beg, const int end)
{
	int sum, u, v, head, tail, i ;
	int e ;
	sum = 0 ;

	while (true)
	{
		MEM (level, -1) ;
		head = tail = 0 ;
		q[tail++] = beg ;
		level[beg] = 0 ;

		while (head < tail)
		{
			u = q[head++] ;
			for (e = vertex[u] ; e != -1 ; e = net[e].n)
			{
				v = net[e].v ;
				if (net[e].c > 0 && -1 == level[v])
				{
					level[v] = level[u] + 1 ;
					if (end == v)
					{
						head = tail ;
						break ;
					}
					q[tail++] = v ;
				}
			}
		}

		if (-1 == level[end])
			break ;
		
		u = beg ;
		tail = 0 ;

		while (true)
		{
			if (end == u)
			{
				int flow = INF, qbreak ;
				for (i = 0 ; i < tail ; ++i)
				{
					e = q[i] ;
					// flow >= net[e].c 会消耗更多时间
					if (flow > net[e].c)
					{
						flow = net[e].c ;
						qbreak = i ;
					}
				}
				sum += flow ;
				for (i = 0 ; i < tail ; ++i)
				{
					e = q[i] ;
					net[e].c -= flow ;
					net[e^1].c += flow ;
				}

				// 这样写超时：
				// e = q[qbreak] ;
				// tail = qbreak + 1 ;
				u = net[q[qbreak]].u ;
				tail = qbreak ;
			}

			for (e = vertex[u] ; e != -1 ; e = net[e].n)
				if (net[e].c > 0 && level[u]+1 == level[net[e].v])
					break ;

			if (-1 == e)
			{
				if (tail == 0)
					break ;
				level[net[q[--tail]].v] = -1 ;
				u = net[q[tail]].u ;
			}
			else
			{
				u = net[e].v ;
				q[tail++] = e ;
			}
		}
	}
	return sum ;
}

int main()
{
	int i ;
	int ans, tmpans, low, hig, mid ;
	while (scanf ("%d%d%d", &n, &p, &t) != EOF)
	{
		init();
		hig = 0 ;
		low = 1000000 ;
		for (i = 1 ; i <= p ; ++i)
		{
			scanf ("%d%d%d", &ed[i].u, &ed[i].v, &ed[i].c) ;
			low = min(ed[i].c, low) ;
			hig = max(ed[i].c, hig) ;
		}

		while (low <= hig)
		{
			mid = (low + hig) / 2 ;
			makegraph (mid) ;
			if ((tmpans = dinic(1, n)) >= t)
			{
				ans = mid ;
				hig = mid - 1 ;
			}
			else
				low = mid + 1 ;
		}
		printf ("%d\n", ans) ;
	}
	return 0 ;
}