BZOJ1834 [ZJOI2010]network 网络扩容

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

网络流训练好题。。。但是要给差评！蒟蒻表示这就是板子题，然后做了半个小时T T

先跑一边最大流，得到第一问答案ans。

第二问：原先的边不动，费用为0。

然后对每条边在上面再加一条边，流量为inf，费用为修改费用。

n向T连一条边，流量为ans + k，费用为0。

跑一边费用流即可。

  1 /**************************************************************
  2     Problem: 1834
  3     User: rausen
  4     Language: C++
  5     Result: Accepted
  6     Time:64 ms
  7     Memory:1296 kb
  8 ****************************************************************/
  9  
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <algorithm>
 13  
 14 using namespace std;
 15 const int N = 1005;
 16 const int M = 10005;
 17 const int inf = (int) 1e9;
 18  
 19 struct Edges {
 20     int x, y, c, w;
 21 } E[M];
 22  
 23 struct edges {
 24     int next, to, f, cost;
 25     edges() {}
 26     edges(int _n, int _t, int _f, int _c) : next(_n), to(_t), f(_f), cost(_c) {}
 27 } e[M << 1];
 28  
 29 int n, m, k, last_ans;
 30 int S, T;
 31 int first[N], tot;
 32 int q[N], d[N], g[N];
 33 bool v[N];
 34  
 35 inline int read() {
 36     int x = 0, sgn = 1;
 37     char ch = getchar();
 38     while (ch < ‘0‘ || ‘9‘ < ch) {
 39         if (ch == ‘-‘) sgn = -1;
 40         ch = getchar();
 41     }
 42     while (‘0‘ <= ch && ch <= ‘9‘) {
 43         x = x * 10 + ch - ‘0‘;
 44         ch = getchar();
 45     }
 46     return sgn * x;
 47 }
 48  
 49 inline void Add_Edges(int x, int y, int f, int c) {
 50     e[++tot] = edges(first[x], y, f, c), first[x] = tot;
 51     e[++tot] = edges(first[y], x, 0, -c), first[y] = tot;
 52 }
 53  
 54 bool bfs() {
 55     memset(d, 0, sizeof(d));
 56     q[1] = S, d[S] = 1;
 57     int l, r, x, y;
 58     for (l = r = 1; l != (r + 1) % N; (++l) %= N)
 59         for (x = first[q[l]]; x; x = e[x].next){
 60             y = e[x].to;
 61             if (!d[y] && e[x].f)
 62                 q[(++r) %= N] = y, d[y] = d[q[l]] + 1;
 63         }
 64  
 65     return d[T];
 66 }
 67    
 68 int dinic(int p, int limit) {
 69     if (p == T || !limit) return limit;
 70     int x, y, tmp, rest = limit;
 71     for (x = first[p]; x; x = e[x].next)
 72         if (d[y = e[x].to] == d[p] + 1 && e[x].f && rest) { 
 73             tmp = dinic(y, min(rest, e[x].f));
 74             rest -= tmp;
 75             e[x].f -= tmp, e[x ^ 1].f += tmp;
 76             if (!rest) return limit;
 77         }
 78     if (limit == rest) d[p] = 0;
 79     return limit - rest;
 80 }
 81    
 82 int Dinic() {
 83     int res = 0, x;
 84     while (bfs())
 85         res += dinic(S, inf);
 86     return res;
 87 }
 88  
 89 void work1() {
 90     int i;
 91     memset(first, 0, sizeof(first));
 92     for (i = tot = 1; i <= m; ++i)
 93         Add_Edges(E[i].x, E[i].y, E[i].c, 0);
 94     S = 1, T = n;
 95     printf("%d ", last_ans = Dinic());
 96 }
 97  
 98 inline int calc() {
 99     int flow = inf, x;
100     for (x = g[T]; x; x = g[e[x ^ 1].to])
101         flow = min(flow, e[x].f);
102     for (x = g[T]; x; x = g[e[x ^ 1].to])
103         e[x].f -= flow, e[x ^ 1].f += flow;
104     return flow;
105 }
106   
107 bool spfa() {
108     int x, y, l, r;
109     for (x = 1; x <= T; ++x)
110         d[x] = inf;
111     d[S] = 0, v[S] = 1, q[0] = S;
112     for(l = r = 0; l != (r + 1) % N; ++l %= N) {
113         for (x = first[q[l]]; x; x = e[x].next)
114             if (d[q[l]] + e[x].cost < d[y = e[x].to] && e[x].f) {
115                 d[y] = d[q[l]] + e[x].cost;
116                 g[y] = x;
117                 if (!v[y])
118                     q[(++r) %= N] = y, v[y] = 1;
119             }
120         v[q[l]] = 0;
121     }
122     return d[T] != inf;
123 }
124  
125 inline int work() {
126     int res = 0;
127     while (spfa())
128         res += calc() * d[T];
129     return res;
130 }
131  
132 void work2() {
133     int i;
134     memset(first, 0, sizeof(first));
135     for (i = tot = 1; i <= m; ++i) {
136         Add_Edges(E[i].x, E[i].y, E[i].c, 0);
137         Add_Edges(E[i].x, E[i].y, inf, E[i].w);
138     }
139     Add_Edges(n, n + 1, last_ans + k, 0);
140     S = 1, T = n + 1;
141     printf("%d\n", work());
142 }
143  
144 int main() {
145     int i;
146     n = read(), m = read(), k = read();
147     for (i = 1; i <= m; ++i)
148         E[i].x = read(), E[i].y = read(), E[i].c = read(), E[i].w = read();
149     work1();
150     work2();
151     return 0;
152 }