Codechef 14.12 RIN 网络流+最小割

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;

#define inf 0x3f3f3f3f
struct Solver {
	static const int V = 100010;
	static const int E = 1000010;
	int head[V], nxt[E], flow[E], to[E], ind, d[V];
	void reset() {
		ind = 0;
		memset(head, -1, sizeof head);
	}
	void addedge(int a, int b, int c) {
		int q = ind++;
		to[q] = b;
		nxt[q] = head[a];
		head[a] = q;
		flow[q] = c;
	}
	void make(int a, int b, int c) {
		addedge(a, b, c);
		addedge(b, a, 0);
	}
	bool bfs(int s, int t, int l, int r) {
		static int q[V], fr, ta, i, j;
		for (i = l; i <= r; ++i)
			d[i] = -1;
		fr = ta = 0;
		d[q[ta++] = s] = 0;
		while (fr != ta) {
			i = q[fr++];
			for (j = head[i]; j != -1; j = nxt[j])
				if (flow[j] && d[to[j]] == -1)
					d[q[ta++] = to[j]] = d[i] + 1;
		}
		return d[t] != -1;
	}
	int dinic(int p, int t, int Maxflow) {
		if (p == t)
			return Maxflow;
		int last = Maxflow;
		for (int j = head[p]; j != -1; j = nxt[j]) {
			if (flow[j] && d[to[j]] == d[p] + 1) {
				int toflow = dinic(to[j], t, last > flow[j] ? flow[j] : last);
				if (toflow) {
					flow[j] -= toflow;
					flow[j ^ 1] += toflow;
					if (!(last -= toflow))
						return Maxflow;
				}
			}
		}
		d[p] = -1;
		return Maxflow - last;
	}
	int Maxflow(int s, int t, int l, int r) {
		int ans = 0;
		while (bfs(s, t, l, r))
			ans += dinic(s, t, inf);
		return ans;
	}
}g;

int node[110][110];
int main() {
	int n, m, k, x, a, b;
	cin >> n >> m >> k;
	int i, j, id = 0;
	for (i = 1; i <= n; ++i)
		for (j = 0; j <= m; ++j)
			node[i][j] = ++id;
	g.reset();
	for (i = 1; i <= n; ++i) {
		for (j = 1; j <= m; ++j) {
			cin >> x;
			if (x == -1)
				g.make(node[i][j - 1], node[i][j], inf);
			else
				g.make(node[i][j - 1], node[i][j], 100 - x);
		}
	}
	int s = 0, t = ++id;
	for (i = 1; i <= n; ++i) {
		g.make(s, node[i][0], inf);
		g.make(node[i][m], t, inf);
	}
	while (k--) {
		cin >> a >> b;
		for (i = 1; i <= m; ++i)
			g.make(node[a][i - 1], node[b][i], inf);
	}
	
	printf("%.2lf\n", (n * 100 - g.Maxflow(s, t, 0, id)) / (double)n);
	
	return 0;
}