POJ 3422: Kaka's Matrix Travels

http://poj.org/problem?id=3422

http://hos.ac/slides/20150319_flow.pdf
ここのp69に載っている問題と同じ。

負辺があるが、グラフが特殊な形をしているので、dijkstraで求めても最短経路が求まり、ポテンシャルも正しく求まる。

これではつまらないので負辺を取り除く方法を考えた。

http://snuke.hatenablog.com/entry/2017/06/07/115821

上のすぬけさんのブログと蟻本を参考にした。

言い換えると今解きたい問題は、dv(s)=-K, dv(t)=K,それ以外dv(v)=0の時の最小費用循環流問題なので、
スーパーノードS,Tを作り、そこから適切にsやtに辺を張ることで実現できる。

これでもACが取れましたといいたいところだが、辺が増えすぎてTLEした。

負辺を含む最小費用流について(Attack the Moles) - sigma425のブログ
ここに書いてあるが、今している変形はこのブログの3に相当し、FがNくらい増えて、オーダーが悪くなることがわかる。

ACしたの

int N, K;

int main() {
	scanf("%d%d", &N, &K);
	int s = 0, t = N * N * 2 - 1;
	MCF::init(N * N * 2);
	rep(i, 0, N) {
		rep(j, 0, N) {
			int id = i * N + j;
			int a; scanf("%d", &a);
			MCF::add_edge(id, id + N * N, 1, -a);
			MCF::add_edge(id, id + N * N, K, 0);
			if(i != N - 1) {
				MCF::add_edge(id + N * N, id + N, K, 0);
			}
			if(j != N - 1) {
				MCF::add_edge(id + N * N, id + 1, K, 0);
			}
		}
	}
	printf("%d\n", -MCF::get(s, t, K));
	return 0;
}

負辺を取り除いたの(TLE)

//minimum cost circularation
namespace MCC { //init before you use it. //negative edges ok.

	struct edge { int to, cap, cost, rev; };

	int V; //num of vertex
	vector<edge> G[MAX_V];
	int h[MAX_V];
	int dist[MAX_V];
	int prevv[MAX_V], preve[MAX_V];
	int S[MAX_V];
	int off;

	void init(int v) {
		V = v;
		//memset(S, 0, sizeof(S));
		//rep(i, 0, V + 2) G[i].clear();
	}

	void add_edge(int from, int to, int cap, int cost) {
		if(cost >= 0) {
			G[from].push_back((edge){to, cap, cost, (int)G[to].size()});
			G[to].push_back((edge){from, 0, -cost, (int)G[from].size() - 1});
		}
		else {
			off += cap * cost;
			S[from] += cap; S[to] -= cap;
			G[to].push_back((edge){from, cap, -cost, (int)G[from].size()});
			G[from].push_back((edge){to, 0, cost, (int)G[to].size() - 1});
		}
	}

	void set_d(int v, int d) { S[v] += d; }

	int impl(int s, int t, int f) {
		int res = 0;
		memset(h, 0, sizeof(h));
		while(f > 0) {
			priority_queue<pi, vector<pi>, greater<pi> > que;
			fill(dist, dist + V, inf);
			dist[s] = 0;
			que.push(pi(0, s));
			while(!que.empty()) {
				pi p = que.top(); que.pop();
				int v = p.sec;
				if(dist[v] < p.fst) continue;
				rep(i, 0, (int)G[v].size()) {
					edge &e = G[v][i];
					if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
						dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
						prevv[e.to] = v;
						preve[e.to] = i;
						que.push(pi(dist[e.to], e.to));
					}
				}
			}
			if(dist[t] == inf) return -1;
			rep(v, 0, V) h[v] += dist[v];

			int d = f;
			for(int v = t; v != s; v = prevv[v]) {
				d = min(d, G[prevv[v]][preve[v]].cap);
			}
			f -= d;
			res += d * h[t];
			for(int v = t; v != s; v = prevv[v]) {
				edge &e = G[prevv[v]][preve[v]];
				e.cap -= d;
				G[v][e.rev].cap += d;
			}
		}
		return res;
	}

	int get() { //u,v,cap,cost
		int f = 0;
		int s = V, t = V + 1;
		rep(i, 0, V) {
			if(S[i] > 0) add_edge(i, t, S[i], 0);
			if(S[i] < 0) {
				add_edge(s, i, -S[i], 0);
				f += -S[i];
			}
		}
		/*
		rep(i, 0, V) {
			rep(j, 0, (int)G[i].size()) {
				debug(i, G[i][j].to, G[i][j].cost);
			}
		}
		*/
		V += 2;
		return impl(s, t, f) + off;
	}
}

int N, K;

int main() {
	scanf("%d%d", &N, &K);
	int s = 0, t = N * N * 2 - 1;
	MCC::init(N * N * 2);
	MCC::set_d(s, -K);
	MCC::set_d(t, K);

	rep(i, 0, N) {
		rep(j, 0, N) {
			int id = i * N + j;
			int a; scanf("%d", &a);
			MCC::add_edge(id, id + N * N, 1, -a);
			MCC::add_edge(id, id + N * N, K, 0);
			if(i != N - 1) {
				MCC::add_edge(id + N * N, id + N, K, 0);
			}
			if(j != N - 1) {
				MCC::add_edge(id + N * N, id + 1, K, 0);
			}
		}
	}
	printf("%d\n", -MCC::get());
	return 0;
}