【最大流+dinic+二分】北大 poj 2455 Secret Milking Machine
/* 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:9799773panyanyany2455Accepted1900K282MSC++3943B2012-02-12 21:46:03Test Data :7 9 21 2 22 3 53 7 51 4 14 3 14 5 75 7 11 6 36 7 3Review :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 ;};intn, p, t, eCnt ;intlevel[MAXN], q[MAXN], vertex[MAXN] ;EDGEnet[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 ;}elselow = mid + 1 ;}printf ("%d\n", ans) ;}return 0 ;}