Cod sursa(job #1397971)

Utilizator stefanzzzStefan Popa stefanzzz Data 23 martie 2015 21:15:53
Problema Taramul Nicaieri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>
#define MAXN 120
using namespace std;

const int off = 110, start = 105, fin = 106;
int n, cap[2 * MAXN][2 * MAXN], fx[2 * MAXN][2 * MAXN];
int bk[2 * MAXN], x, totfx;
vector<int> G[MAXN];

bool BFS(){
	queue<int> q;
	int x;

	memset(bk, 0, sizeof(bk));
	
	q.push(start);
	while(!q.empty()){
		x = q.front(); q.pop();
		for(auto y: G[x])
			if(!bk[y] && fx[x][y] < cap[x][y]){
				bk[y] = x;
				q.push(y);
			}
	}

	return bk[fin] != 0;
}

int main(){
	freopen("harta.in", "r", stdin);
	freopen("harta.out", "w", stdout);
	int i, j;

	scanf("%d", &n);
	for(i = 1; i <= n; i++){
		scanf("%d %d", &cap[start][i], &cap[i + off][fin]);
		G[start].push_back(i);
		G[i + off].push_back(fin);
	}
	
	for(i = 1; i <= n; i++)
		for(j = off + 1; j <= off + n; j++)
			if(i + off != j){
				cap[i][j] = 1;
				G[i].push_back(j);
				G[j].push_back(i);
			}
	
	while(BFS()){
		for(i = off + 1; i <= off + n; i++)
			if(fx[i][fin] < cap[i][fin]){
				x = i;
				while(bk[x]){
					if(fx[bk[x]][x] == cap[bk[x]][x]) break;
					x = bk[x];
				}
				if(bk[x]) continue;
				
				x = i;
				fx[x][fin]++;
				fx[fin][x]--;
				totfx++;
				while(bk[x]){
					fx[bk[x]][x]++;
					fx[x][bk[x]]--;
					x = bk[x];
				}
			}
	}

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

	return 0;
}