最大权闭合图

  1 /* 最大权闭合图 
  2 肥水不流外人田
  3 闭合子图：在有向图中出边指向本身
  4 建图方法：
  5 在原有的图的基础上，将边的容量设置为inf建图，
  6 点权为正则从源点S到该点建立一条边，
  7 反之则建立该点到汇点的边，边权为点权的绝对值
  8 
  9 玄学证明：
 10 假设v1为一个闭合图，v2 = ~v1, S = {{s}&v1}, T = {{t}&v2}
 11 那么 C(v1,v2) = 0, 又有C(s, t) = 0
 12 则 C(S, T) = C(s, v2) + C(v1, t)
 13 然后又因为这个闭合图里头这种建图方式的最小割与闭合图是简单割(只在闭合图这里使用这个概念)
 14 所以 C(s, v2) 就是v2中正点点权和 sv2+
 15 C(v1, t) 则是v1中负点点权和的绝对值 sv1- > 0
 16 C(S, T) = (sv2+) + (sv1-)
 17 sv1 = (sv1+) + (- sv1-)
 18 C(S, T) + sv1 = (sv1+) + (sv2+) = sv+
 19 sv1 = (sv+ - C(S,T))
 20 结论：
 21 最大权闭合图的最大权 = 正值和 - 最小割容量
 22 感性的猜想：
 23 正值和就是源点能够提供的流的最大值sv+,
 24 而这个建图方式优点依然是一个割应该是简单割，
 25 靠近S的集合分为在v1和v2内的，减去简单割在v2+的部分说明是去除了v1集合以外的正数
 26 剪掉了靠近T集合的说明是去掉了v1内流出的量，也就是负数和
 27 */
 28 
 29 const int maxn = 55000 + 10;
 30 const int maxm = (50000 * 3 + 5000) * 2 + 10;
 31 const int inf = 0x3f3f3f3f;
 32 int n, m, S, T;
 33 int h[maxn], tot, e[maxm], f[maxm], ne[maxm];
 34 int q[maxn], d[maxn], cur[maxn];
 35 void add (int u, int v, int c) {
 36   e[tot] = v, f[tot] = c, ne[tot] = h[u], h[u] = tot ++;
 37   e[tot] = u, f[tot] = 0, ne[tot] = h[v], h[v] = tot ++;
 38 }
 39 bool bfs() {
 40   int hh = 0, tt = -1;
 41   memset(d, -1, sizeof(d));
 42   q[++tt] = S;
 43   d[S] = 0;
 44   cur[S] = h[S];
 45   while (hh <= tt) {
 46     int u = q[hh ++];
 47     for (int i = h[u]; ~i; i = ne[i])
 48     {
 49       int v = e[i];
 50       if (d[v] == -1 && f[i])
 51       {
 52         d[v] = d[u] + 1;
 53         cur[v] = h[v];
 54         if (v == T) return true;
 55         q[++tt] = v;
 56       }
 57     }
 58   }
 59   return false;
 60 }
 61 int dfs(int u, int limit)
 62 {
 63   if (u == T) return limit;
 64   int flow = 0;
 65   for (int i = cur[u]; ~i && flow < limit; i = ne[i])
 66   {
 67     cur[u] = i;
 68     int v = e[i];
 69     if (d[v] == d[u] + 1 && f[i])
 70     {
 71       int t = dfs(v, min(limit - flow, f[i]));
 72       if (!t) d[v] = -1;
 73       flow += t;
 74       f[i] -= t;
 75       f[i^1] += t;
 76     }
 77   }
 78   return flow;
 79 }
 80 int dinic() {
 81   int r = 0, flow;
 82   while (bfs())
 83     while (flow = dfs(S, inf))
 84       r += flow;
 85   return r;
 86 }
 87 int main () {
 88   scd2(n, m);
 89   S = 0;
 90   T = n + m + 1;
 91   memset(h, -1, sizeof(h));
 92   for (int i = 1; i <= n; ++i) {
 93     int val;
 94     scd(val);
 95     add(m + i, T, val);
 96   }
 97   int sum = 0;
 98   for (int i = 1; i <= m; ++i) {
 99     int a, b, c;
100     scd3(a, b, c);
101     add(S, i, c);
102     add(i, m + a, inf);
103     add(i, m + b, inf);
104     sum += c;
105   }
106   prdln(sum - dinic());
107   return 0;
108 }
View Code