Cod sursa(job #5456)

Utilizator IgnitionMihai Moraru Ignition Data 12 ianuarie 2007 15:58:04
Problema Taramul Nicaieri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <stdio.h>
#include <limits.h>
#include <vector>
#include <queue>

using namespace std;

#define MN (209)
#define pb push_back

int c[MN][MN], f[MN][MN], p[MN], m[MN];
vector<int> g[MN];
int N, F, S = 0, D;
queue<int> q;

int bfs(int s, int t)
{
	int n1, n2, i;

	memset(p, -1, sizeof(p));
	memset(m, 0, sizeof(m));
	m[s] = LONG_MAX;
	for(; !q.empty(); q.pop());
	for(q.push(s); !q.empty(); q.pop()) {
		n1 = q.front();
		for(i = 0; i < g[n1].size(); ++ i) {
			n2 = g[n1][i];
			if(c[n1][n2]-f[n1][n2] > 0 && p[n2] == -1) {
				m[n2] = min(m[n1], c[n1][n2]-f[n1][n2]);
				p[n2] = n1;
				if(n2 != t)
					q.push(n2);
			}
		}
	}
	return m[t];
}

void ek()
{
	int n1, n2;
	for(; bfs(S, D); F += m[D]) {
		for(n1 = D; n1 != S; n1 = n2) {
			n2 = p[n1];
			f[n2][n1] += m[D];
			f[n1][n2] -= m[D];
		}
	}
}

int main()
{
	int i, j;

	freopen("harta.in", "r", stdin);
	freopen("harta.out", "w", stdout);

	scanf("%d", &N);
	for(D = 2*N+1, i = 1; i <= N; ++ i) {
		g[0].pb(i); g[i].pb(0); scanf("%d", &c[0][i]);
		g[N+i].pb(D); g[D].pb(N+i); scanf("%d", &c[N+i][D]);
	}

	for(i = 1; i <= N; ++ i) for(j = 1; j <= N; ++ j) if(i != j) {
		g[i].pb(N+j); c[i][N+j] = 1;
		g[N+j].pb(i);
	}

	/*
	for(i = 0; i <= D; ++ i, printf("\n")) for(printf("%d:", i), j = 0; j < g[i].size(); ++ j)
		printf(" %d", g[i][j]);
	for(i = 0; i <= D; ++ i, printf("\n")) for(j = 0; j <= D; ++ j)
		printf("%d ", c[i][j]);
	for(i = 0; i <= D; ++ i, printf("\n")) for(j = 0; j <= D; ++ j)
		printf("%d ", f[i][j]);
		*/

	ek();

	/*
	for(printf("%d\n", F), i = 0; i <= D; ++ i, printf("\n")) for(printf("%d:", i), j = 0; j <= D; ++ j)
		printf(" %d", f[i][j]);
		*/

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

	return 0;
}