BZOJ1570 [JSOI2008]Blue Mary的旅行

浏览数：21 / 时间：2015年06月09日

建分层图，每一层表示一天的情况

从S向第0层的1号点连边，每层的n向T连INF的边

枚举天数，每多一天就多建一层然后跑最大流，如果当前流量大于人数则输出答案

由于路径长度不会超过n，因此tot个人走这条路径总天数不会超过tot + n，故只需要建tot + n层即可

  1 /**************************************************************
  2     Problem: 1570
  3     User: rausen
  4     Language: C++
  5     Result: Accepted
  6     Time:24 ms
  7     Memory:15936 kb
  8 ****************************************************************/
  9  
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <algorithm>
 13  
 14 using namespace std;
 15 const int N = 55;
 16 const int M = 5005;
 17 const int inf = 1e8;
 18  
 19 inline int read() {
 20     int x = 0;
 21     char ch = getchar();
 22     while (ch < ‘0‘ || ‘9‘ < ch)
 23         ch = getchar();
 24     while (‘0‘ <= ch && ch <= ‘9‘) {
 25         x = x * 10 + ch - ‘0‘;
 26         ch = getchar();
 27     }
 28     return x;
 29 }
 30  
 31 struct Edge {
 32     int x, y, z;
 33      
 34     inline void read_in() {
 35         x = read(), y = read(), z = read();
 36     }
 37 } E[M];
 38  
 39 struct edge {
 40     int next, to, f;
 41     edge() {}
 42     edge(int _n, int _t, int _f) : next(_n), to(_t), f(_f) {}
 43 } e[M << 8];
 44  
 45 int n, m, t;
 46 int S, T, ans;
 47 int first[M], tot = 1;
 48 int d[M], q[M];
 49  
 50 inline void Add_Edges(int x, int y, int f) {
 51     e[++tot] = edge(first[x], y, f), first[x] = tot;
 52     e[++tot] = edge(first[y], x, 0), first[y] = tot;
 53 }
 54  
 55 #define y e[x].to
 56 #define p q[l]
 57 bool bfs() {
 58   int l, r, x;
 59   memset(d, -1, sizeof(d));
 60   d[q[1] = S] = 1;
 61   for (l = r = 1; l != r + 1; ++l)
 62     for (x = first[p]; x; x = e[x].next)
 63       if (!~d[y] && e[x].f) {
 64     d[q[++r] = y] = d[p] + 1;
 65     if (y == T) return 1;
 66       }
 67   return 0;
 68 }
 69 #undef p
 70  
 71 int dfs(int p, int lim) {
 72   if (p == T || !lim) return lim;
 73   int x, tmp, rest = lim;
 74   for (x = first[p]; x && rest; x = e[x].next) 
 75     if (d[y] == d[p] + 1 && ((tmp = min(e[x].f, rest)) > 0)) {
 76       rest -= (tmp = dfs(y, tmp));
 77       e[x].f -= tmp, e[x ^ 1].f += tmp;
 78       if (!rest) return lim;
 79     }
 80   if (rest) d[p] = -1;
 81   return lim - rest;
 82 }
 83 #undef y
 84  
 85 int Dinic() {
 86   int res = 0;
 87   while (bfs())
 88     res += dfs(S, inf);
 89   return res;
 90 }
 91  
 92 int main() {
 93     int i, j;
 94     n = read(), m = read(), t = read();
 95     for (i = 1; i <= m; ++i) E[i].read_in();
 96     S = 1, T = 2;
 97     Add_Edges(S, 3, t);
 98     for (i = 1; i <= n + t; ++i) {
 99         for (j = 1; j <= m; ++j)
100             Add_Edges(i * n - n + E[j].x + 2, i * n + E[j].y + 2, E[j].z);
101         for (j = 1; j <= n; ++j)
102             Add_Edges(i * n - n + j + 2, i * n + j + 2, inf);
103         Add_Edges(i * n + n + 2, T, inf);
104         ans += Dinic();
105         if (ans == t) {
106             printf("%d\n", i);
107             return 0;
108         }
109     }
110 }