二次联通门 : BZOJ 2039: [2009国家集训队]employ人员雇佣
/*BZOJ 2039: [2009国家集训队]employ人员雇佣最小割先全部雇佣每个人向汇点连边后源点分别向i,j连边i,j之间连容量为2 * a[i][j]的边如果用两个，就不用割用一个或都不用，就要割掉2 *a[i][j]答案即为利润之和减去割掉的值*/ #include <cstdio> #include <iostream> #define rg registerinline void read (int &n) { rg char c = getchar ();for (n = 0; !isdigit (c); c = getchar ());for (; isdigit (c); n = n * 10 + c - '0', c = getchar ()); } #define Max 1020 int S, T; #define INF 1e9 namespace net {const int MaxE = 4000100;int _n[MaxE], _v[MaxE], list[Max], _f[MaxE], EC = 1, d[Max], q[Max], tc[Max];inline void In (int u, int v, int f) { _v[++ EC] = v, _n[EC] = list[u], list[u] = EC, _f[EC] = f;_v[++ EC] = u, _n[EC] = list[v], list[v] = EC, _f[EC] = 0;}bool Bfs () {int h = 1, t = 1; q[t] = S; rg int i, n;for (i = 0; i <= T; ++ i) d[i] = -1;for (d[S] = 0; h <= t; ++ h)for (n = q[h], i = list[n]; i; i = _n[i])if (_f[i] && d[_v[i]] < 0) {d[_v[i]] = d[n] + 1, q[++ t] = _v[i];if (_v[i] == T) return true; }return false;}int Flowing (int n, int f) {if (n == T || f == 0) return f;int p, r = 0;for (rg int &i = tc[n]; i; i = _n[i])if (_f[i] && d[_v[i]] == d[n] + 1) { p = Flowing (_v[i], std :: min (_f[i], f));if (p > 0) { r += p, f -= p, _f[i] -= p, _f[i ^ 1] += p;if (f == 0) return r;}}if (r != f) d[n] = -1; return r;}int Dinic () { int res = 0;for (; Bfs (); res += Flowing (S, INF))for (rg int i = 0; i <= T; ++ i) tc[i] = list[i];return res;} } int a[Max][Max]; int main (int argc, char *argv[]) {int N, x, res = 0; read (N); S = 0, T = N + 1; rg int i, j;for (i = 1; i <= N; ++ i) read (x), net :: In (i, T, x);for (i = 1; i <= N; ++ i)for (j = 1; j <= N; ++ j) read (a[i][j]), res += a[i][j];for (i = 1; i <= N; ++ i)for (j = 1 + i; j <= N; ++ j)net :: In (S, i, a[i][j]), net :: In (S, j, a[i][j]), net :: In (i, j, a[i][j]<< 1), net :: In (j, i, a[i][j] << 1);printf ("%d", res - net :: Dinic ());return 0; }
