bzoj-1834 network 网络扩容【网络流】

　　这题就是复习下网络流。
  1 #include <bits/stdc++.h>
  2 #define rep(i, a, b) for (int i = a; i <= b; i++)
  3 #define drep(i, a, b) for (int i = a; i >= b; i--)
  4 #define REP(i, a, b) for (int i = a; i < b; i++)
  5 #define mp make_pair
  6 #define pb push_back
  7 #define clr(x) memset(x, 0, sizeof(x))
  8 #define xx first
  9 #define yy second
 10 using namespace std;
 11 typedef long long i64;
 12 typedef pair<int, int> pii;
 13 const int inf = ~0U >> 1;
 14 const i64 INF = ~0ULL >> 1;
 15 //********************************
 16 
 17 const int maxn = 1005, maxm = 5005;
 18 
 19 struct Ed {
 20     int u, v, nx, c, w; Ed() {}
 21     Ed(int _u, int _v, int _nx, int _c, int _w) :
 22         u(_u), v(_v), nx(_nx), c(_c), w(_w) {}
 23 } E[maxm << 2];
 24 int G[maxn], edtot, cur[maxn];
 25 void addedge(int u, int v, int c, int w) {
 26     E[edtot] = Ed(u, v, G[u], c, w);
 27     G[u] = edtot++;
 28     E[edtot] = Ed(v, u, G[v], 0, -w);
 29     G[v] = edtot++;
 30 }
 31 
 32 int level[maxn], s , t;
 33 bool bfs() {
 34     static int que[maxn]; int qh(0), qt(0);
 35     clr(level);
 36     level[que[++qt] = s] = 1;
 37     while (qh != qt) {
 38         int x = que[++qh];
 39         for (int i = G[x]; i != -1; i = E[i].nx) if (!level[E[i].v] && E[i].c) {
 40             level[que[++qt] = E[i].v] = level[x] + 1;
 41         }
 42     }
 43     return !!level[t];
 44 }
 45 int dfs(int u, int rm) {
 46     if (u == t) return rm;
 47     int rm1 = rm;
 48     for (int &i = cur[u]; i != -1; i = E[i].nx) {
 49         if (level[E[i].v] == level[u] + 1 && E[i].c) {
 50             int flow = dfs(E[i].v, min(rm, E[i].c));
 51             E[i].c -= flow, E[i ^ 1].c += flow;
 52             if ((rm -= flow) == 0) break;
 53         }
 54     }
 55     if (rm1 == rm) level[u] = 0;
 56     return rm1 - rm;
 57 }
 58 
 59 int dis[maxn], vis[maxn];
 60 bool spfa() {
 61     static int que[maxn]; int qh(0), qt(0);
 62     memset(dis, 0x3f, sizeof(dis));
 63     clr(vis);
 64     dis[que[++qt] = s] = 0, vis[s] = 1;
 65     while (qh != qt) {
 66         int x = que[++qh]; vis[x] = 0;
 67         for (int i = G[x]; i != -1; i = E[i].nx) {
 68             if (E[i].c && dis[E[i].v] > dis[x] + E[i].w) {
 69                 dis[E[i].v] = dis[x] + E[i].w;
 70                 if (!vis[E[i].v]) que[++qt] = E[i].v, vis[E[i].v] = 1;
 71             }
 72         }
 73     }
 74     return dis[t] != 0x3f3f3f3f;
 75 }
 76 int ret;
 77 int dinic(int u, int rm) {
 78     vis[u] = 1;
 79     if (u == t) return rm;
 80     int rm1 = rm;
 81     for (int i = G[u]; i != -1; i = E[i].nx) {
 82         if (dis[E[i].v] == dis[u] + E[i].w && E[i].c && !vis[E[i].v]) {
 83             int flow = dinic(E[i].v, min(rm , E[i].c));
 84             E[i].c -= flow, E[i ^ 1].c += flow;
 85             ret += flow * E[i].w;
 86             if ((rm -= flow) == 0) break;
 87         }
 88     }
 89     if (rm1 == rm) dis[u] = 0;
 90     return rm1 - rm;
 91 }
 92 
 93 int main() {
 94     int n, m, K;
 95     scanf("%d%d%d", &n, &m, &K);
 96     memset(G, -1, sizeof(G));
 97     rep(i, 1, m) {
 98         int x, y, c, w;
 99         scanf("%d%d%d%d", &x, &y, &c, &w);
100         addedge(x, y, c, w);
101         addedge(x, y, c, 0);
102     }
103     s = 0, t = n + 1; addedge(s, 1, 0x3f3f3f3f, 0), addedge(n, t, 0x3f3f3f3f, 0);
104     int ans(0);
105     while (bfs()) memcpy(cur, G, sizeof(G)), ans += dfs(s, 0x3f3f3f3f);
106     printf("%d ", ans >> 1);
107     for (int i = 0; i <= edtot; i += 2) {
108         if (E[i].w == 0) E[i].c += E[i ^ 1].c, E[i ^ 1].c = 0;
109         else E[i].c = 0x3f3f3f3f, E[i ^ 1].c = 0;
110         if (E[i].u == s) E[i].c = (ans >> 1) + K;
111     }
112     while (spfa()) clr(vis), dinic(s, 0x3f3f3f3f);
113     printf("%d
", ret);
114 }
View Code
bzoj-1834 network 网络扩容 【网络流】

bzoj-1834 network 网络扩容【网络流】
