RT

TLE on #3 & #5

本地跑了 1min，

我可能需要一个 1/100 的常数（（（

不是确实有人 dinic 过了嘛。。。

#include <bits/stdc++.h>
#define LL long long

namespace Basic {
	template <typename Temp>
	inline void read(Temp & res) {
		Temp fh = 1; res = 0; char ch = getchar();
		for(; !isdigit(ch); ch = getchar()) if(ch == '-') fh = -1;
		for(; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ '0');
		res = res * fh;
	}
	template <typename Temp> inline void Checkmax(Temp & num, Temp comp) {if(comp > num) num = comp;}
	template <typename Temp> inline void Checkmin(Temp & num, Temp comp) {if(comp < num) num = comp;}
}

using namespace std;
using namespace Basic;

const int Maxn = 1e6 + 5;

const int Maxm = Maxn * 3;

struct e {
	int to, nxt, f;
} b[Maxm << 1];
int head[Maxn], ecnt = 1;
inline void add(int u, int v, int fl) {b[++ecnt] = (e){v, head[u], fl}; head[u] = ecnt;}
int n, m, a, ans, maxflow;

int dep[Maxn], cur[Maxn]; 

queue<int> q;
inline bool bfs() {
	memset(dep, 0, sizeof(dep));
	while(!q.empty()) q.pop();
	q.push(1); dep[1] = 1; cur[1] = head[1];
	while(!q.empty()) {
		int tnow = q.front(); q.pop();
		for(register int i = head[tnow]; i; i = b[i].nxt) {
			int tto = b[i].to, tf = b[i].f;
			if((!tf) || dep[tto]) continue;
			dep[tto] = dep[tnow] + 1;
			cur[tto] = head[tto];
			q.push(tto);
			if(tto == n * m) return 1;
		}
	}
	return 0;
}

int dfs(int t, int flow) {
	if(t == n * m) return flow;
	int rest = flow, k, i;
	for(i = cur[t]; i && rest; i = b[i].nxt) {
		int tto = b[i].to, tf = b[i].f;
		if((!tf) || (dep[tto] != dep[t] + 1)) continue;
		k = dfs(tto, min(flow, tf));
		b[i].f -= k;
		b[i ^ 1].f += k;
		rest -= k;
		if(!k) dep[tto] = 0;
	}
	cur[t] = i;
	return flow - rest;
}

int main() {
	//freopen("3.in", "r", stdin);
	read(n); read(m);
	for(register int i = 1, s = 0; i <= n; ++i, s += m) {
		for(register int j = 1; j < m; ++j) {
			read(a);
			add(s + j, s + j + 1, a);
			add(s + j + 1, s + j, a);
		}
	}
	for(register int i = 1, s = 0; i < n; ++i, s += m) {
		for(register int j = 1; j <= m; ++j) {
			read(a);
			add(s + j, s + j + m, a);
			add(s + j + m, s + j, a);
		}
	}
	for(register int i = 1, s = 0; i < n; ++i, s += m) {
		for(register int j = 1; j < m; ++j) {
			read(a);
			add(s + j, s + j + m + 1, a);
			add(s + j + m + 1, s + j, a);
		}
	}
	while(bfs()) {
		memcpy(cur, head, sizeof(cur));
		ans += dfs(1, 0x7fffffff >> 1);
	}
	printf("%d", ans);
	return 0;
}