Cod sursa(job #754309)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 1 iunie 2012 16:29:53
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

ifstream in("harta.in");
ofstream out("harta.out");

#define N 230
#define inf 10000000

int n, c[N][N], f[N][N], p[N], s, d;
vector<int> v[N];

bool bf() {
	queue<int> q;
	int i, el;
	
	for(i = s; i<=d; ++i)
		p[i] = -1;
	
	q.push(s);
	p[s] = 0;
	
	while(!q.empty()) {
		el = q.front();
		q.pop();
		if(el!=d)
		for(vector<int>::iterator it = v[el].begin(); it!=v[el].end(); ++it)
			if(p[*it] == -1 && c[el][*it] > f[el][*it]) {
			
				p[*it] = el;
			
				q.push(*it);
			}
	}
	
	return p[d]!=-1;
}

void flux() {
	int j, smin;
	vector<int>::iterator it;
	
	while(bf())
		for(it = v[d].begin(); it!=v[d].end(); ++it)
		if(c[*it][d] > f[*it][d]) {
			
			smin = c[*it][d] - f[*it][d];
			
			for(j = *it; j!=s; j = p[j])
				if(c[p[j]][j] - f[p[j]][j] < smin)
					smin = c[p[j]][j] - f[p[j]][j];
			
			f[*it][d] += smin;
			f[d][*it] -= smin;
			
			for(j = *it; j!=s; j = p[j]) {
				
				f[p[j]][j] += smin;
				f[j][p[j]] -= smin;
			}
		}
}

int main() {
	int i, j, x, y, ss = 0;
	
	in >> n;
	
	s = 1; d = 2 * (n + 1);
	
	for(i = 1; i<=n; ++i) {
		in >> x >> y;
		ss+=y;
		
		c[s][i + 1] = x;
		c[i + n + 1][d] = y;
		
		v[s].push_back(i + 1);
		v[i + 1].push_back(s);
		v[i + n + 1].push_back(d);
		v[d].push_back(i + n + 1);
		
		for(j = 1; j<=n; ++j) if(j!=i) {
			
			c[j + 1][i + n + 1] = 1;
			v[j + 1].push_back(i + n + 1);
			v[i + n + 1].push_back(j + 1);
		}
	}
	
	flux();
	
	out << ss << "\n";
	
	for(i = 1; i<=d/2; ++i)
		for(j = 1; j<=d/2; ++j) if(i!=j && f[i + 1][j + n + 1])
			out << i << " " << j << "\n";
	
	return 0;
}