相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3577
神犇题解:http://www.cnblogs.com/clrs97/p/4403242.html
解题报告
之前一直都是线段树优化建图
这题需要用$ST$表来优化建图
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int INF = 1e9; const int N = 500000; const int M = 2000000; int S,T,E,tot,A,B,Y,X,n2[2][70][70][8]; int head[N],nxt[M],to[M],flow[M],n1[2][70][70]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void AddEdge(int u, int v, int f) { assert(u); assert(v); to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; } class NetworkFlow{ int dis[N],cur[N]; queue<int> que; public: inline int MaxFlow() { int ret = 0; while (BFS()) { memcpy(cur, head, sizeof(cur)); ret += DFS(S, INF); } return ret; } private: inline bool BFS() { memset(dis, 60, sizeof(dis)); dis[S] = 0; for (que.push(S); !que.empty(); que.pop()) { int w = que.front(); for (int i = head[w]; i; i = nxt[i]) { if (flow[i] && dis[to[i]] > INF) { dis[to[i]] = dis[w] + 1; que.push(to[i]); } } } return dis[T] <= INF; } inline int DFS(int w, int f) { if (w == T) { return f; } else { int ret = 0; for (int &i = cur[w]; i; i = nxt[i]) { if (flow[i] && dis[to[i]] == dis[w] + 1) { int tmp = DFS(to[i], min(f, flow[i])); ret += tmp; f -= tmp; flow[i] -= tmp; flow[i ^ 1] += tmp; if (!f) { break; } } } return ret; } } }Dinic; int main() { #ifdef DBG freopen("11input.in", "r", stdin); #endif X = read(); Y = read(); A = read(); B = read(); S = ++tot; T = ++tot; E = 1; for (int i = 1; i <= X; ++i) { for (int j = 1; j <= Y; ++j) { n1[0][i][j] = ++tot; n1[1][i][j] = ++tot; AddEdge(n1[0][i][j], n1[1][i][j], read()); } } for (int i = X; i; --i) { for (int j = Y; j; --j) { for (int a = 0, len = 1; i + len - 1 <= X && j + len - 1 <= Y; ++a, len <<= 1) { n2[0][i][j][a] = ++tot; n2[1][i][j][a] = ++tot; if (!a) { AddEdge(n2[0][i][j][a], n1[0][i][j], INF); AddEdge(n1[1][i][j], n2[1][i][j][a], INF); } else { int llen = len >> 1; AddEdge(n2[0][i][j][a], n2[0][i][j][a - 1], INF); AddEdge(n2[0][i][j][a], n2[0][i + llen][j][a - 1], INF); AddEdge(n2[0][i][j][a], n2[0][i][j + llen][a - 1], INF); AddEdge(n2[0][i][j][a], n2[0][i + llen][j + llen][a - 1], INF); AddEdge(n2[1][i][j][a - 1], n2[1][i][j][a], INF); AddEdge(n2[1][i][j + llen][a - 1], n2[1][i][j][a], INF); AddEdge(n2[1][i + llen][j][a - 1], n2[1][i][j][a], INF); AddEdge(n2[1][i + llen][j + llen][a - 1], n2[1][i][j][a], INF); } } } } for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= A; ++i) { p0 = ++tot; p1 = ++tot; w = read(); x1 = read(); y1 = read(); x2 = read(); y2 = read(); AddEdge(S, p0, INF); AddEdge(p0, p1, w); int len = x2 - x1 + 1, lg = 0, d = 1; for (; (d << 1) <= len; lg++, d <<= 1); AddEdge(p1, n2[0][x1][y1][lg], INF); AddEdge(p1, n2[0][x1][y2 - d + 1][lg], INF); AddEdge(p1, n2[0][x2 - d + 1][y1][lg], INF); AddEdge(p1, n2[0][x2 - d + 1][y2 - d + 1][lg], INF); } for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= B; ++i) { p0 = ++tot; p1 = ++tot; w = read(); x1 = read(); y1 = read(); x2 = read(); y2 = read(); AddEdge(p0, p1, w); AddEdge(p1, T, INF); int len = x2 - x1 + 1, lg = 0, d = 1; for (; (d << 1) <= len; lg++, d <<= 1); AddEdge(n2[1][x1][y1][lg], p0, INF); AddEdge(n2[1][x1][y2 - d + 1][lg], p0, INF); AddEdge(n2[1][x2 - d + 1][y1][lg], p0, INF); AddEdge(n2[1][x2 - d + 1][y2 - d + 1][lg], p0, INF); } assert(tot < N); assert(E < M); printf("%d\n", Dinic.MaxFlow()); return 0; }