要分成两坨对吧。。 所以显然最小割
但是不兹辞啊。。
最小割是最小的啊 求最大费用怎么玩啊
那咱们就把所有费用都加起来，减掉一个最小的呗
但是两个属于不同集合的点贡献的价值是负的啊
网络流怎么跑负的啊
那咱就交换一下呗
原图是二分图啊，把另一部分与S和T连边的流量换一下就好啦。
注意哦 n和m可能为1 所以累加C的时候写成ans += C[i][j] * (4 - (i == 1 || i == n) - (j == 1 || j == m));就错啦。
要么在加边的时候累加，要么写成ans += C[i][j] * ((i != 1) + (i != n) + (j != 1) + (j != m));
1 #include2 #include 3 #include 4 #include 5 #include 6 #define rep(i, a, b) for(int i = (a), _end = (b); i <= _end; ++i) 7 8 using namespace std; 9 10 void setIO(const string& s) { 11 freopen((s + ".in").c_str(), "r", stdin); 12 freopen((s + ".out").c_str(), "w", stdout); 13 } 14 template Q read(Q& x) { 15 static char c, f; 16 for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1; 17 for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0'; 18 if(f) x = -x; 19 return x; 20 } 21 template Q read() { 22 static Q x; read(x); return x; 23 } 24 25 // ISAP 26 const int N = 100 * 100 + 10, M = 100 * 100 * 4 + 10, INF = ~0u >> 1; 27 28 struct Edge { 29 int to, adv; 30 Edge *next; 31 Edge(int to = 0, int adv = 0, Edge *next = 0) : to(to), adv(adv), next(next) {} 32 }pool[M * 2], *pis = pool, *fir[N], *pre[N]; 33 34 void AddEdge(int u, int v, int w, int b = 0) { 35 fir[u] = new(pis++) Edge(v, w, fir[u]); 36 fir[v] = new(pis++) Edge(u, w * b, fir[v]); 37 } 38 39 Edge *inv(Edge *p) { 40 return pool + ((p - pool) ^ 1); 41 } 42 43 int d[N], q[N], ql, qr; 44 45 namespace ISAP { 46 int n, s, t; 47 int num[N]; 48 Edge *cur[N]; 49 50 void insert(int u, int dis) { 51 if(d[u] == n) { 52 d[u] = dis; 53 q[qr++] = u; 54 } 55 } 56 57 void BFS() { 58 for(int u = 1; u <= n; u++) { 59 d[u] = n; 60 } 61 ql = qr = 0; 62 insert(t, 0); 63 while(ql ^ qr) { 64 int u = q[ql++]; 65 for(Edge *p = fir[u]; p; p = p->next) if(inv(p)->adv){ 66 insert(p->to, d[u] + 1); 67 } 68 } 69 } 70 71 int Augment() { 72 int a = INF; 73 for(int u = t; u != s; u = inv(pre[u])->to) { 74 a = min(a, pre[u]->adv); 75 } 76 for(int u = t; u != s; u = inv(pre[u])->to) { 77 pre[u]->adv -= a; 78 inv(pre[u])->adv += a; 79 } 80 return a; 81 } 82 83 int Maxflow() { 84 memset(num, 0, sizeof num); 85 BFS(); 86 for(int u = 1; u <= n; u++) { 87 cur[u] = fir[u]; 88 num[d[u]]++; 89 } 90 for(int i = 1; i < d[s]; i++) { 91 if(!num[i]) return 0; 92 } 93 int flow = 0; 94 for(int u = s; d[s] < n; ) { 95 if(u == t) { 96 flow += Augment(); 97 u = s; 98 } 99 int ok = 0;100 for(Edge *&p = cur[u]; p; p = p->next) if(p->adv) {101 int v = p->to;102 if(d[v] + 1 == d[u]) {103 pre[u = v] = p;104 ok = 1;105 break;106 }107 }108 if(!ok) {109 int &dis = d[u];110 if(!--num[dis]) break;111 dis = n;112 for(Edge *p = (cur[u] = fir[u]); p; p = p->next) if(p->adv) {113 dis = min(dis, d[p->to] + 1);114 }115 num[dis]++;116 if(u != s) u = inv(pre[u])->to;117 }118 }119 return flow;120 }121 122 int main(int _n, int _s, int _t) {123 n = _n, s = _s, t = _t;124 return Maxflow();125 }126 }127 128 int n, m;129 130 int encode(int x, int y) {131 return (x - 1) * m + y;132 }133 134 const int maxn = 100 + 10;135 136 int A[maxn][maxn], B[maxn][maxn], C[maxn][maxn];137 138 int main() {139 #ifdef DEBUG140 freopen("in.txt", "r", stdin);141 freopen("out.txt", "w", stdout);142 #endif143 144 read(n), read(m);145 int ans = 0;146 rep(i, 1, n) rep(j, 1, m) ans += read(A[i][j]);147 rep(i, 1, n) rep(j, 1, m) ans += read(B[i][j]);148 rep(i, 1, n) rep(j, 1, m) read(C[i][j]);149 int s = n * m + 1, t = s + 1;150 rep(i, 1, n) rep(j, 1, m) {151 int u = encode(i, j);152 if((i ^ j) & 1) swap(A[i][j], B[i][j]);153 AddEdge(s, u, A[i][j]);154 AddEdge(u, t, B[i][j]);155 if(i < n) AddEdge(u, encode(i + 1, j), C[i][j] + C[i+1][j], 1), ans += C[i][j] + C[i+1][j];156 if(j < m) AddEdge(u, encode(i, j + 1), C[i][j] + C[i][j+1], 1), ans += C[i][j] + C[i][j+1];157 }158 159 printf("%d\n", ans - ISAP::main(t, s, t));160 161 return 0;162 }