/* 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 ;
}
