BOJ 2679 - Route Redundancy(맨체스터의 도로)

  A에서 B로 갈 수 있는 모든 경로의 차의 수 최대값은 최대 유량으로 충분히 가능하다. 하지만 또 하나가 있는게 이 중에서도 한 경로만 사용했을 때, 최대값을 구해서 앞서 구한 모든 경로의 차의 최대값과 한 경로의 차의 수 최대값의 비율을 계산하라고 한다. 단순 최대유량 문제만 내기엔 부족했나보다.

  편의상 A에서 B로 가는 모든 경로의 차의 수 최대값을 X라고 하고, 한 경로의 차의 수 최대값을 Y라고하면 구하고자 하는 값은 Y/X가 된다.

  X는 단순 최대 유량으로 구해서 계산하며 Y는 backtracking으로 정의하여 계산한다. Y를 구할 때, 기저 사례는 B를 만날 때까지고, 재귀를 돌며 방문했던 정점은 다시 방문하지 않도록 한다. 재귀의 반환값은 현재 정점에서 방문 가능한 정점 중에서 차를 최대한 많이 보낼 수 있는 수와 현재 방문하기 이전 정점까지의 경로의 최대한 차가 지나다닐 수 있는 값과 비교하여 작은 값을 비교해준다. 하나의 길(경로)에 대해 차가 지나다니려면 그 경로에 존재하는 모든 도로 중 최소값을 기준으로 차가 지나다닐 수 있기 때문이다.

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int min_v(int a, int b) { return a < b ? a : b; }
int max_v(int a, int b) { return a > b ? a : b; }
const int MAX_V = 1001;
struct Edge {
	int v, rn, f, c;
	void setData(int to, int rev_n, int flow, int cap) {
		v = to, rn = rev_n, f = flow, c = cap;
	}
	int rc() { return c - f; }
	void af(int amt, vector<Edge> adj[]) {
		f += amt;
		adj[v][rn].f -= amt;
	}
};
vector<Edge> adj[MAX_V];
void addEdge(int u, int v, int c) {
	Edge uv, vu;
	uv.setData(v, adj[v].size(), 0, c);
	vu.setData(u, adj[u].size(), 0, 0);
	adj[u].push_back(uv);
	adj[v].push_back(vu);
}

bool visit[MAX_V];
int dfs(int n, const int& t, int c) {
	if (n == t) return c;
	
	int ret = 0;
	for (Edge& e : adj[n])
		if (e.c > 0 && !visit[e.v]) {
			visit[e.v] = 1;
			ret = max_v(ret, dfs(e.v, t, e.c));
			visit[e.v] = 0;
		}

	return min_v(ret, c);
}

int main() {
	int T, N, E, A, B, i, u,v,c,allpath,singlepath, prev[MAX_V];
	Edge* path[MAX_V];
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d%d", &N, &E, &A, &B);
		for (i = 0; i < N; i++) adj[i].clear();
		while (E--) {
			scanf("%d%d%d", &u, &v, &c);
			addEdge(u, v, c);
		}
		allpath = singlepath = 0;
		while (1) {
			memset(prev, -1, sizeof(prev));
			memset(path, 0, sizeof(path));
			queue<int> q;
			q.push(A);
			while (!q.empty()) {
				u = q.front(), q.pop();
				for (Edge& e : adj[u])
					if (e.rc() && prev[e.v] == -1) {
						prev[e.v] = u;
						path[e.v] = &e;
						q.push(e.v);
					}
			}
			if (prev[B] == -1) break;
			int amt = 1e9;
			for (i = B; i != A; i = prev[i]) amt = min_v(amt, path[i]->rc());
			for (i = B; i != A; i = prev[i]) path[i]->af(amt, adj);
			allpath += amt;
		}
		memset(visit, 0, sizeof(visit));
		visit[A] = 1;
		singlepath = dfs(A, B, 1e9);
		printf("%.3lf\n", (double)allpath / singlepath);
	}
	return 0;
}