CPSCO2019 Session2 F - Treasure Collector (700) - くるのプログラミング記録

リンク
F - Treasure Collector
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
問題文は長いので割愛

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
個人的に見た目は区間dp、ギリ4乗通る気がするので(通らないかも)
まあ違っていて。

結論を言うと"燃やす埋める"をします。

そもそもフローを知らない人はFord FulkersonかDinicのライブラリを作ろう。
これとかを解くと良さそう。
https://atcoder.jp/contests/abc010/tasks/abc010_4

”燃やす埋める”を知らない人はググろう。たくさん記事が出てくるので。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
以下、フローと燃やす埋めるは知識としてある前提で。

まず頂点の持ち方。
この問題で2状態のどちらかを選ぶようなものは何か？
そもそも2状態とは？

結論としては頂点は $N × N$ の全てのマス。
すべてのコインはx方向あるいはy方向のどちらかで回収される、これが2状態になる。

絵を描いてみると分かることだが、コイン目線でx方向あるいはy方向を決めると回収してくれるロボットは一意に決まる。
直感的には4通りありそうだけど制約的にそうならない。
言われるとまあ自明かも。

次に辺の張り方。

１．まず禁止するための辺を張る。
これは簡単。
例えばあるコインをx方向で回収してもらうとしたときに、ロボットのいるマスまでの間にy方向を選ぶコインがあってはならない。
なので
ある頂点を決めたときに、ロボットから遠い側の頂点が向かってくる方向に対して垂直に動くようなパターンは許されない。
これを満たすようにコストが無限大の辺を張っていく。

２．コストの辺について。
全マスにコスト $1$ の辺を張ると終わりになってしまう。
ここが難しい。
$i$ 行目におけるx方向のコストを愚直に考えると(ロボットとの距離) $/A_i$ となる。

$i$ 行目におけるx方向のコストは
.. 6 5 5 5 4 4 4 3 3 3 2 2 2 1 1 1 r 1 1 1 2 2 2 3 3 3 ...
$A_i = 3$ のときこんな感じ。rはロボットのいる点。

これに合わせて辺を張るとそれはそれでコスト過多。重複があるので。
ここで見方を変えると、同じコストの頂点について一度コストを払うとどこまでも進めると言い直すことができる。

$i$ 行目におけるx方向のコストは
.. 6 0 0 5 0 0 4 0 0 3 0 0 2 0 0 1 r 1 0 0 2 0 0 3 0 0 ...
$A_i = 3$ のときこんな感じ。rはロボットのいる点。

これでかなりマシになった。でもまだ重複がある。
よく考えると、例えばコスト $6$ の点を使うときロボットに対して同じ側のコスト $1$ の頂点は必ず使われているはずである。
またこれはグラフ上でも先に作った禁止辺によって達成されている。
なのでコストを累積する必要はなく全て $1$ でよい。その結果

$i$ 行目におけるx方向のコストは
.. 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 r 1 0 0 1 0 0 1 0 0 ...
$A_i = 3$ のときこんな感じ。rはロボットのいる点。

これに合わせて辺を張ると最小カット容量がそのまま答えとなる。
以下コード。

#include <bits/stdc++.h>
using namespace std;

template <class T> class Dinic {
public:
	struct info {
		int to, rev;
		T cap;
	};
	T ini, inf;
	vector<vector<info>> edge;
	vector<int> level, iter;

	Dinic(int N, T ini, T inf) : edge(N), level(N), iter(N), ini(ini), inf(inf) {
		// do nothing
	}

	void make_edge(int from, int to, T cap) {
		edge[from].push_back({ to, (int)edge[to].size(), cap });
		edge[to].push_back({ from, (int)edge[from].size() - 1, ini });
	}

	void bfs(int start) {
		for (int i = 0; i < level.size(); ++i) level[i] = -1;
		queue<int> q;
		level[start] = 0;
		q.push(start);
		while (q.size()) {
			int from = q.front();
			q.pop();
			for (auto& e : edge[from]) {
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[from] + 1;
					q.push(e.to);
				}
			}
		}
	}

	T dfs(int from, int goal, T flow) {
		if (from == goal) return flow;
		for (int& i = iter[from]; i < edge[from].size(); ++i) {
			auto& e = edge[from][i];
			if (e.cap <= 0 || level[from] >= level[e.to]) continue;
			T dflow = dfs(e.to, goal, min(flow, e.cap));
			if (dflow <= 0) continue;
			e.cap -= dflow;
			edge[e.to][e.rev].cap += dflow;
			return dflow;
		}
		return ini;
	}

	T maxflow(int start, int goal) {
		T maxflow = ini;
		while (1) {
			bfs(start);
			if (level[goal] < 0) return maxflow;
			for (int i = 0; i < iter.size(); ++i) iter[i] = 0;
			T flow;
			while ((flow = dfs(start, goal, inf))>0) maxflow += flow;
		}
	}
};

int main() {
	int N; cin >> N;
	vector<int> p(N),a(N);
	for(int i = 0; i < N; ++i) cin >> p[i];
	for(int i = 0; i < N; ++i) p[i]--;
	for(int i = 0; i < N; ++i) cin >> a[i];
	
	//コストを前計算
	vector<vector<int>> cx(N,vector<int>(N,0)),cy(N,vector<int>(N,0));
	for(int n = 0; n < N; ++n){
		int y = n, x = p[n], z = a[n];
		for(int i = 1; y + i < N ; ++i) cy[y+i][x] = !((i-1)%z);
		for(int i = 1; 0 <= y - i; ++i) cy[y-i][x] = !((i-1)%z);
		for(int j = 1; x + j < N ; ++j) cx[y][x+j] = !((j-1)%z);
		for(int j = 1; 0 <= x - j; ++j)	cx[y][x-j] = !((j-1)%z);
	}

	int inf = 12345;
	Dinic<int> dinic(N*N+2,0,inf);

	//コストの辺
	for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j){
		dinic.make_edge(N*N,i*N+j,cy[i][j]);
		dinic.make_edge(i*N+j,N*N+1,cx[i][j]);
	}

	//禁止辺
	for(int n = 0; n < N; ++n){
		int y = n, x = p[n], z = a[n];
		cy[y][x] = 1;
		cx[y][x] = 1;
		for(int i = 2; y + i < N ; ++i) dinic.make_edge((y+i-1)*N+x,(y+i)*N+x,inf);
		for(int i = 2; 0 <= y - i; ++i) dinic.make_edge((y-i+1)*N+x,(y-i)*N+x,inf);
		for(int j = 2; x + j < N ; ++j) dinic.make_edge(y*N+x+j,y*N+x+j-1,inf);
		for(int j = 2; 0 <= x - j; ++j)	dinic.make_edge(y*N+x-j,y*N+x-j+1,inf);
	}

	//最大流
	cout << dinic.maxflow(N*N,N*N+1) << endl;

    return 0;
}