消輪法解最小費用フロー(poj 2175 Evaluation Plan)

消輪アルゴリズム:まず最大の流れを求めて、更にGfの中で負の費用の輪を探してそれに沿って広がります
改良:追加アーク(s,t)を増加する、費用がs-t最大費用路(例えばVC)より大きく、アーク上の初期流がs-t最大流(例えばsから出発するアーク容量と1を加える)より大きい消輪アルゴリズムは、できるだけ多くの流を追加アークから移動させるので、得られる流は最大流である.最後に追加アークに余裕がある可能性があります.無視してください.
実際の効果:最小費用拡張アルゴリズムは、Gfの任意のs-t路とt-sが必ず負の費用圏を構成するため
最悪の場合分析:負の料金圏O(VE)を探すたびに、料金を1回だけ更新し、ECM回(Mが最大料金、Cが容量)を必要とし、疎図では総時間複雑度O(VE^2 CM)=O(V^3 CM)
用途:効率が極めて低いため、消輪アルゴリズムは一般的に最適解であるか否かを判断するために用いられ、最適解を求めるために用いられない.
定理:1つの費用フローが最小費用フローである要件は、この費用フローの残量ネットワークに負の費用ループがないことである.
poj 2175 Evaluation Plan題意:n個の建物、m個の避難所があり、各建物の座標と所有者および各避難所の座標と容量が知られている.建物iと避難所jとの距離は、|xi-xj|+|yi-yj|+1である.今、建物の人を避難所に避難させるように要求しています.建物iにx[i][j]の人がj避難所に行き、全員が避難所を見つけたことを保証する案が示されている.このスキームは総距離が最も小さいかどうかを聞いて、もし1つの所与のスキームよりもっと良いスキームを出力しなければ(SPJ)解法ができます:残留ネットワークを観察して、ソースから建物の間は必ず満流で、そのため1本のi->sの長さが0の辺を建てるだけです;いずれかの建物と避難所の点対(i,j)について、原図のi->j流量は正無限であるため、長さが2点間の距離の辺を1本加える.元のスキームでi->jに流量がある場合、j->iは2点間の負の距離の長さのエッジを追加する.各避難所jについて、提案されたjの和が0より大きい場合、t−>jの長さが0のエッジが構築される.jより小さい容量の場合、j->iの長さが0のエッジを作成します.tをソース点としてspfaを1回行い、リングが発見されるとリング内の順方向辺流量+1、逆方向辺流量-1となり、得られる解は元のスキームよりも優れている.
特に注意:ある点vのエンキュー回数が点数より大きい場合、vがリング内の点であることは説明できませんが、vのある前駆者は必ずリング内の点です.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
public class Evacation2175 {
	int maxn = 210, inf = 1 << 28;
	class MINCOST {
		int E[][] = new int[maxn][maxn], p[] = new int[maxn], n;
		int queue[] = new int[maxn], d[] = new int[maxn];
		void init(int n) {
			this.n = n;
			for (int i = 0; i <= n; i++)
				Arrays.fill(E[i], inf);
		}
		boolean vis[] = new boolean[maxn];
		int cnt[] = new int[maxn];
		int spfa(int s, int t) {
			Arrays.fill(d, inf);
			Arrays.fill(p, -1);
			Arrays.fill(vis, false);
			d[s] = 0;
			vis[s] = true;
			int head = 0, tail = 0, v, u;
			queue[(tail++) % maxn] = s;
			while (tail != head) {
				u = queue[(head++) % maxn];
				vis[u] = false;
				for (v = 0; v < n; v++) {
					if (E[u][v] == inf)
						continue;
					if (d[u] + E[u][v] < d[v]) {
						d[v] = d[u] + E[u][v];
						p[v] = u;
						if (!vis[v]) {
							queue[(tail++) % maxn] = v;
							vis[v] = true;
							if (++cnt[v] > n)
								return v;
						}//   
					}//   
				}//    
			}// while
			return -1;
		}
		boolean solve(int s, int t, int nt) {
			int idx = spfa(t, s);
			if (idx == -1)
				return true;
			else {
				int v = idx;
				Arrays.fill(vis, false);
				while (!vis[v]) {
					vis[v] = true;
					v = p[v];
				}
				idx = v;
				do {
					if (v > nt && p[v] <= nt)
						ans[p[v]][v - nt]++;
					if (v <= nt && p[v] > nt)
						ans[v][p[v] - nt]--;
					v = p[v];
				} while (v != idx);
				return false;
			}
		}
	}
	int dis(int i, int j) {
		return Math.abs(x[i] - x[j]) + Math.abs(y[i] - y[j]) + 1;
	}
	MINCOST mc = new MINCOST();
	int x[] = new int[maxn], y[] = new int[maxn], cap[] = new int[maxn];
	int ans[][] = new int[maxn][maxn], n, m;
	void init() throws IOException {
		n = nextInt();
		m = nextInt();
		for (int i = 1; i <= n; i++) {
			x[i] = nextInt();
			y[i] = nextInt();
			cap[i] = nextInt();
		}
		for (int i = 1; i <= m; i++) {
			x[i + n] = nextInt();
			y[i + n] = nextInt();
			cap[i] = nextInt();
		}
	}
	int sum[] = new int[maxn];
	void build() throws IOException {
		mc.init(m + n + 2);
		Arrays.fill(sum, 0);
		for (int i = 1; i <= n; i++)
			mc.E[i][0] = 0;
		for (int i = 1; i <= m; i++)
			mc.E[m + n + 1][n + i] = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) {
				ans[i][j] = nextInt();
				mc.E[i][j + n] = dis(i, j + n);
				if (ans[i][j] > 0)
					mc.E[j + n][i] = -dis(i, j + n);
				sum[j] += ans[i][j];
			}
		for (int i = 1; i <= m; i++) {
			if (sum[i] > 0)
				mc.E[m + n + 1][i + n] = 0;
			if (sum[i] < cap[i])
				mc.E[i + n][m + n + 1] = 0;
		}
	}
	void run() throws IOException {
		init();
		build();
		if (mc.solve(0, m + n + 1, n))
			System.out.println("OPTIMAL");
		else {
			System.out.println("SUBOPTIMAL");
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j < m; j++)
					System.out.print(ans[i][j] + " ");
				System.out.println(ans[i][m]);
			}
		}
	}

	StreamTokenizer in = new StreamTokenizer(new BufferedReader(
			new InputStreamReader(System.in)));
	int nextInt() throws IOException {
		in.nextToken();
		return (int) in.nval;
	}
	public static void main(String[] args) throws IOException {
		new Evacation2175().run();
	}
}