Cod sursa(job #540004)

Utilizator cosmyoPaunel Cosmin cosmyo Data 23 februarie 2011 16:44:57
Problema Taramul Nicaieri Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 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;
vector<int> a[N];

int BFS() {
	int k, i, j;
	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];
		for(i = 0; i < a[k].size(); ++i)
			if(c[k][a[k][i]] > f[k][a[k][i]] && !v[a[k][i]]) {
				t[a[k][i]] = k;
				v[a[k][i]] = 1;
				cd[++cd[0]] = a[k][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], a[0].push_back(i), a[i].push_back(0), a[n + i].push_back(2 * n + 1), a[2 * n + 1].push_back(n + i);
	t[0] = -1;
	for(i = 1; i <= n; ++i)
		for(j = 1; j <= n; ++j)
			if(i != j)
			 c[i][n + j] = 1, a[i].push_back(n + j), a[n + j].push_back(i);
	S = 0;
	D = 2 * n + 1;
	int u;
	for(;BFS();) {
//		printf("\n");
		for(i = n + 1; i <= 2 * n; ++i)
			if(v[i]) {
				k = D;
				t[k] = i;
				r = INF;
				while(k) {
					r = min(r,c[t[k]][k] - f[t[k]][k]);
//					printf("%d ", k);
					k = t[k];
				}
//				printf("%d\n", r);
				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] == c[i][j + n] && f[i][j + n] > 0)
				++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;
}