Cod sursa(job #540008)

Utilizator cosmyoPaunel Cosmin cosmyo Data 23 februarie 2011 17:01:25
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include<cstdio>
#include<vector>
using namespace std;
const int N = 205;
const int INF = 0x3f3f3f3f;
int n, dint[N], dies[N], c[N][N], f[N][N], t[N], v[N], S, D;

int BFS() {
	int k, i, j, p, u;
	int cd[N];
	cd[0] = 1;
	cd[1] = S;
	for(i = 1; i <= 2 * n + 1; ++i)
		v[i] = t[i] = 0;
	v[S] = 1;
	for(j = 1; j <= cd[0]; ++j) {
		k = cd[j];
		p = 1;
		u = 2 * n + 1;
		for(i = p; i <= u; ++i)
			if(c[k][i] > f[k][i] && !v[i]) {
				t[i] = k;
				v[i] = 1;
				if(i == 2 * n + 1)
					return 1;
				cd[++cd[0]] = i;
			}
	}
	return v[D];
}
int main() {
	freopen("harta.in", "r", stdin);
	freopen("harta.out", "w", stdout);
	int i, j, k, r;
	scanf("%d", &n);
	for(i = 1; i <= n; ++i)
		scanf("%d %d", &dies[i], &dint[i]);

	for(i = 1; i <= n; ++i)
		c[0][i] = dies[i], c[n + i][2 * n + 1] = dint[i];
	t[0] = -1;
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= n; ++j)
			if(i != j)
			 c[i][n + j] = 1;
	S = 0;
	D = 2 * n + 1;
	int u;
	for(;BFS();) {
				k = D;
				r = INF;
				while(k) {
					r = min(r,c[t[k]][k] - f[t[k]][k]);
					k = t[k];
				}
				k = D;
				while(k) {
					f[k][t[k]] -= r;
					f[t[k]][k] += r;
					k = t[k];
				}	
	}
	int nr = 0;
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= n; ++j)
			if(f[i][j + n] == 1)
				++nr;
	printf("%d\n", nr);

	for(i = 1; i <= n; ++i)
		for(j = 1; j <= n; ++j)
			if(f[i][j + n] == 1)
				printf("%d %d\n", i, j);

	return 0;
}