259 – Software Allocation

You’re given 10 computers and a set of programs that need to be executed. A computer cannot multitask. Each problem needs to run on a computer of a specific set. Find an assignment of the programs to the computers.

We map the problem to a graph and solve via maximum flow.
We have two layers of nodes; those of the computers and those of the programs. Each computer node is connected to a program node if and only if it can run the program. The source node is connected to all 10 computer nodes and all program nodes are connected to the sink node.
We run Edmond-Karp algorithm and if the maximum flow is less that the number of programs, we can’t find a satisfactory allocation. Otherwise, an allocation is found and can be retrieved by examining the graph.
C++ implementaion with rank 217:

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

#define N 39
int cap[N][N], parent[N], s = 37, t = 38;

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 (int v = 0; v < N; ++v)
			if (parent[v] == -1 && cap[u][v] > 0)
				parent[v] = u, q.push(v);
	}
	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, cap[parent[v]][v]), v = parent[v];
		// update
		v = t;
		mf += f;
		while (parent[v] != v)
			cap[parent[v]][v] -= f, cap[v][parent[v]] += f, v = parent[v];
	}
	return mf;
}

int main() {
	char line[1024], *c, nProg = 1, mf;
	while (true) {
		// init
		memset(cap, 0, sizeof cap);
		for (int i = 0; i < 10; ++i)
			cap[i][t] = 1;
		// input
		nProg = 0;
		while (gets(line) && line[0]) {
			nProg += (cap[s][line[0] - 'A' + 10] = line[1] - '0');
			c = &line[3];
			while (*c != ';')
				cap[line[0] - 'A' + 10][*c - '0'] = 1, ++c;
		}
		// output
		if (!nProg)
			break;
		mf = maxFlow();
		if (mf == nProg)
			for (int i = 0; i < 10; ++i) {
				int j;
				for (j = 0; j < 26; ++j)
					if (cap[i][j + 10])
						break;
				printf("%c", j == 26 ? '_' : j + 'A');
			}
		else
			printf("!");
		printf("\n");
	}
	return 0;
}

11418 – Clever Naming Patterns

You’re given a list of problems each can have one of multiple candidate names. You’re required to pick a name for each problem so that no two problem have names that start with the same latter.

There’s an acceptable brute-force solution. However, a maximum flow solution looks nicer.
We’ll have a source, a sink and two layers of nodes. The first layer contains 26 nodes that represent the alphabet. The second layer contains nodes that represent the problems. Each node in the first layer is connected to the source and each noce in the second layer is connected to the sink. Each problem p that has a candidate name that starts with a letter c is connected to the node that represents that letter (c,p).
If we run the Edmond-Karp maximum flow algorithm we should get a maximum flow equal to the number of problems. By examining the graph after the execution, we can find which letter is assigned to which problem.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cctype>
#include <limits>
#include <string>
#include <queue>
#include <map>
using namespace std;

#define N 54
typedef map<int, int>::iterator itr;
map<int, int> res[N];
int parent[N], s = N - 2, t = N - 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() {
	string str;
	int nCase, nProblem;
	map<char, string> pNames[28];
	cin >> nCase;
	for (int caseI = 0; caseI < nCase; ++caseI) {
		// init
		cin >> nProblem;
		for (int i = 0; i < N; ++i)
			res[i].clear();
		for (int i = 0; i < nProblem; ++i) {
			pNames[i].clear();
			res[s][26 + i] = 1;
			res[i][t] = 1;
		}
		// input
		for (int i = 0, nName; i < nProblem; ++i) {
			cin >> nName;
			for (int j = 0; j < nName; ++j) {
				cin >> str;
				str[0] = toupper(str[0]);
				for (int k = 1; k < str.length(); ++k)
					str[k] = tolower(str[k]);
				pNames[i][str[0]] = str;
				res[str[0] - 'A' + 26][i] = 1;
			}
		}
		// solve
		maxFlow();
		cout << "Case #" << (caseI + 1) << ":\n";
		for (int i = 0; i < nProblem; ++i)
			for (itr it = res[i + 26].begin(); it != res[i + 26].end(); ++it)
				if (!it->second) {
					cout << pNames[it->first][i + 'A'] << endl;
					break;
				}
	}
	return 0;
}

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;
}