Cod sursa(job #370117)

Utilizator adelinasAdelina Spataru adelinas Data 30 noiembrie 2009 11:41:23
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
#define NMAX 205
#define FOR(i, v) for(vector<int>::iterator i = v.begin(); i != v.end(); ++i)
#define INF 2000000000
vector <int> v[NMAX];
queue <int> q;
int F[NMAX][NMAX], C[NMAX][NMAX], viz[NMAX], T[NMAX];
int n, fin;
int min(int x,int y){
	if(x>y) return y;
	return x;
}
int BFS(){
	memset(viz, 0, sizeof(viz));
	q.push(0);
	viz[0] = 1;
	while(!q.empty()){
		int nod = q.front();
		q.pop();
		if(nod == fin ) continue;
		FOR(i, v[nod]){
			if( viz[*i] || C[nod][*i] == F[nod][*i]) continue;
			viz[*i] = 1;
			T[*i] = nod;
			q.push(*i);
		}
	}
	return viz[n];
}
void construiesc_legaturi(){
	int i,j;
	for(i = 1; i <= n; ++i){
		v[0].push_back(i);
		v[i].push_back(0);
	}
	for(i = 1; i <= n; ++i)
		for(j = n+1; j <= 2*n; ++j)
			if(j-n != i) {
				v[i].push_back(j);
				v[j].push_back(i);
				C[i][j] = 1;
			}
	for(i = n+1; i <= 2*n; ++i){
		v[i].push_back(2*n+1);
		v[2*n+1].push_back(i);
	}
}
int main(){
	freopen("harta.in", "r", stdin);
	freopen("harta.out", "w", stdout);
	scanf("%d",&n);
	fin = 2*n + 1;
	for(int i = 1; i <= n; ++i){
		int x, y;
		scanf("%d %d", &x, &y);
		C[0][i] = x;
		C[n+i][2*n+1] = y;
	}
	construiesc_legaturi();	
	while(BFS())
		FOR(i, v[fin]){
			if(C[*i][fin] == F[*i][fin]) continue;
			int flowm = INF;
			T[fin] = *i;
			for(int i = fin; i != 0; i = T[i])
				flowm = min( flowm, C[ T[i] ][ i ] - F[ T[i] ][ i ]);
			if(flowm == 0) continue;
			for(int i = fin; i != 0; i = T[i]){
				F[ T[i] ][ i ] += flowm;
				F[ i ][ T[i] ] -= flowm;
			}
		}
	int c = 0;
	for(int i = 1; i <= n; ++i)
		for(int j = n+1; j <= 2*n; j++)
			if(F[i][j]) c++;
	printf("%d\n", c);
	for(int i = 1; i <= n; ++i)
		for(int j = n+1; j <= 2*n; j++)
			if(F[i][j]) printf("%d %d\n", i, j-n);
	return 0;
}