10480 – Sabotage

You’re given a specification of a country’s network connnection. Find the connections that must be destroyed to speparate two cities in this network. Make sure the connections you pick are of lowest sabotage cost.

This is a minimum cut prolem which can be solved using the Edmond-Karp maximum flow algorithm.

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <limits>
#include <queue>
#include <map>
using namespace std;

#define N 60
typedef map<int, int>::iterator itr;
map<int, int> res[N];
int parent[N], n, s = 0, t = 1;

bool bfs() {
	queue<int> q;
	q.push(s);
	memset(parent, -1, sizeof parent);
	parent[s] = s;
	while (q.size()) {
		int u = q.front();
		q.pop();
		if (u == t)
			return true;
		for (itr it = res[u].begin(); it != res[u].end(); ++it)
			if (parent[it->first] == -1 && it->second > 0)
				parent[it->first] = u, q.push(it->first);
	}
	return false;
}

int maxFlow() {
	int mf = 0, f, v;
	while (bfs()) {
		// min
		v = t;
		f = numeric_limits<int>::max();
		while (parent[v] != v)
			f = min(f, res[parent[v]][v]), v = parent[v];
		// update
		v = t;
		mf += f;
		while (parent[v] != v)
			res[parent[v]][v] -= f, res[v][parent[v]] += f, v = parent[v];
	}
	return mf;
}

int main() {
	int m;
	while (scanf("%d %d", &n, &m) == 2 && (n || m)) {
		// init
		for (int i = 0; i < n; ++i)
			res[i].clear();
		// input
		for (int a, b, c; m; --m)
			scanf("%d %d %d", &a, &b, &c), res[--a][--b] = c, res[b][a] = c;
		// solve
		maxFlow();
		for (int i = 0; i < n; ++i)
			if (parent[i] != -1)
				for (itr it = res[i].begin(); it != res[i].end(); ++it)
					if (parent[it->first] == -1)
						printf("%d %d\n", i + 1, it->first + 1);
		printf("\n");
	}
	return 0;
}