首页 > 代码库 > BZOJ2127 happiness

BZOJ2127 happiness

2024-07-25 08:01:43   218人阅读

很好的网络流题目啦，只不过有点烦，不过这下总算是完全掌握了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 }
View Code

 

BZOJ2127 happiness


联系
我们