BZOJ2127 happiness

浏览数：32 / 时间：2015年06月11日

很好的网络流题目啦，只不过有点烦，不过这下总算是完全掌握了Dinic的精髓。。。

首先考虑建图：

s --> A 权值为a[A] + sigma(他和四周都选全文科的高兴值) / 2

A --> t 权值为b[A] + sigma(他和四周都选全理科的高兴值) / 2

A <--> B 权值为（同时选文科的高兴值+同时选理科的高兴值） / 2

为了解决精度问题，边权先乘以二，最后结果再除以二即可。

但是不知道为什么是对的。。。在此Orz hzwer，要是没有他的程序我就完蛋了。。。

（p.s. 作死小剧场增强版我数组d一开始刚好开了d[10002]，然后t=10002，死活过不了，查了一下午，我也是醉了%>_<%）

  1 /**************************************************************
  2     Problem: 2127
  3     User: rausen
  4     Language: C++
  5     Result: Accepted
  6     Time:2472 ms
  7     Memory:6900 kb
  8 ****************************************************************/
  9   
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <algorithm>
 13   
 14 #define rep(i, n) for (int (i) = 1; (i) <= (n); ++(i))
 15 #define REP for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
 16 using namespace std;
 17 const int inf = (int) 1e9;
 18   
 19 struct edges{
 20     int next, to, f;
 21 } e[500000];
 22   
 23 int n, m, ans, tot = 1, s, t;
 24 int first[10005], q[10005], d[10005];
 25 int w[101][101], a[101][101], b[101][101];
 26   
 27 inline void add_edge(int x, int y, int z){
 28     e[++tot].next = first[x];
 29     first[x] = tot;
 30     e[tot].to = y;
 31     e[tot].f = z;
 32 }
 33   
 34 inline void add_Edge(int x, int y, int z){
 35     add_edge(x, y, z);
 36     add_edge(y, x, 0);
 37 }
 38   
 39 void add_Edges(int x, int y, int z){
 40     add_Edge(x, y, z);
 41     add_Edge(y, x, z);
 42 }
 43   
 44 bool bfs(){
 45     memset(d, 0, sizeof(d));
 46     q[1] = s, d[s] = 1;
 47     int l = 0, r = 1, x, y;
 48     while (l < r){
 49         ++l;
 50         for (x = first[q[l]]; x; x = e[x].next){
 51             y = e[x].to;
 52             if (!d[y] && e[x].f)
 53                 q[++r] = y, d[y] = d[q[l]] + 1;
 54         }
 55     }
 56     return d[t];
 57 }
 58   
 59 int dinic(int p, int limit){
 60     if (p == t || !limit) return limit;
 61     int x, y, tmp, rest = limit;
 62     for (x = first[p]; x; x = e[x].next){
 63         y = e[x].to;
 64         if (d[y] == d[p] + 1 && e[x].f && rest){
 65             tmp = dinic(y, min(rest, e[x].f));
 66             rest -= tmp;
 67             e[x].f -= tmp, e[x ^ 1].f += tmp;
 68             if (!rest) return limit;
 69         }
 70     }
 71     if (limit == rest) d[p] = 0;
 72     return limit - rest;
 73 }
 74   
 75 int Dinic(){
 76     int res = 0, x;
 77     while (bfs())
 78         res += dinic(s, inf);
 79     return res;
 80 }
 81   
 82 void make_graph(){
 83     int X;
 84     rep(i, n - 1) rep(j, m){
 85         scanf("%d", &X);
 86         ans += X, a[i][j] += X, a[i + 1][j] += X;
 87         add_Edges(w[i][j], w[i + 1][j], X);
 88     }
 89     rep(i, n - 1) rep(j, m){
 90         scanf("%d", &X);
 91         ans += X, b[i][j] += X, b[i + 1][j] += X;
 92         add_Edges(w[i][j], w[i + 1][j], X);
 93     }
 94     rep(i, n) rep(j, m - 1){
 95         scanf("%d", &X);
 96         ans += X, a[i][j] += X, a[i][j + 1] += X;
 97         add_Edges(w[i][j], w[i][j + 1], X);
 98     }
 99     rep(i, n) rep(j, m - 1){
100         scanf("%d", &X);
101         ans += X, b[i][j] += X, b[i][j + 1] += X;
102         add_Edges(w[i][j], w[i][j + 1], X);
103     }
104     s =  n * m + 1, t = s + 1;
105     REP{
106         add_Edge(s, w[i][j], a[i][j]);
107         add_Edge(w[i][j], t, b[i][j]);
108     }
109 }
110   
111 int main(){
112     scanf("%d%d", &n, &m);
113     REP{
114         scanf("%d", a[i] + j);
115         ans += a[i][j], a[i][j] <<= 1;
116     }
117     REP{
118         scanf("%d", b[i] + j);
119         ans += b[i][j], b[i][j] <<= 1;
120     }
121     REP w[i][j] = (i - 1) * m + j;
122     make_graph();
123     printf("%d\n", ans - (Dinic() >> 1));
124     return 0;
125 }