Cod sursa(job #218973)

Utilizator andrei.12Andrei Parvu andrei.12 Data 4 noiembrie 2008 16:09:18
Problema Taramul Nicaieri Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<stdio.h>
#include<vector>
#include<queue>

using namespace std;

#define pb push_back
#define lg 105

int n, i, j, prd[lg], c[lg][lg], t[lg][2];
vector<int> v[lg];

int find(){
	int x, i;

	bool fst[lg] = {0};
	memset(prd, 0xff, sizeof(prd));

	queue<int> q;
	q.push(0), fst[0] = 1;

	while (!q.empty()){
		x = q.front(), q.pop();

		for (i = 0; i < (int)v[x].size(); i ++)
			if (!fst[v[x][i]] && c[x][v[x][i]] > 0){
				fst[v[x][i]] = 1;
				prd[v[x][i]] = x;

				q.push(v[x][i]);
			}
	}

	if (!fst[2*n+1])
		return 0;

	int mn = 0x3f3f3f3f;
	
	for (x = 2*n+1; prd[x] != -1; x = prd[x])
		mn = min(mn, c[prd[x]][x]);

	for (x = 2*n+1; prd[x] != -1; x = prd[x]){
		c[prd[x]][x] -= mn;
		c[x][prd[x]] += mn;
	}

	return mn;
}
int flux(){
	int x, rsp = 0;

	do{
		x = find();
		rsp += x;
	}
	while (x > 0);

	return rsp;
}
int main()
{
	freopen("harta.in", "rt", stdin);
	freopen("harta.out", "wt", stdout);

	scanf("%d", &n);
	for (i = 1; i <= n; i ++)
		scanf("%d%d", &t[i][0], &t[i][1]);

	for (i = 1; i <= n; i ++){
		v[0].pb(i), v[i].pb(0), c[0][i] = t[i][0];
		v[i+n].pb(2*n+1), v[2*n+1].pb(i+n), c[i+n][2*n+1] = t[i][1];

		for (j = 1; j <= n; j ++)
			if (i != j)
				v[i].pb(n+j), v[n+j].pb(i), c[i][n+j] = 1;
	}

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

	return 0;
}