Nu aveti permisiuni pentru a descarca fisierul grader_test8.ok

Cod sursa(job #1498388)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 8 octombrie 2015 15:47:15
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

template <typename T>
using mat = vector<vector<T> >;

int flux_max(const int surs, const int dest,
	const mat<int>& adiac, const mat<int>& cap, mat<int>& flux){

	const int n = adiac.size();
	vector<int> tata(n, 0);
	queue<int> de_viz;

	int rez = 0;
	while(true){
		fill(begin(tata), end(tata), -1);
		tata[surs] = surs;
		de_viz.push(surs);
		while(!de_viz.empty()){
			const int cur = de_viz.front();
			de_viz.pop();
			for(const auto next : adiac[cur]){
				if(tata[next] == -1 && cap[cur][next] - flux[cur][next] > 0){
					tata[next] = cur;
					de_viz.push(next); } } }
		if(tata[dest] == -1){
			return rez; }
		for(const auto last : adiac[dest]){
			if(tata[last] != -1 && cap[last][dest] - flux[last][dest] > 0)
				tata[dest] = last;
				int f_min = 1000000000;
				for(int nod = dest; nod != surs && f_min > 0; nod = tata[nod]){
					f_min = min(f_min,
						cap[tata[nod]][nod] - flux[tata[nod]][nod]); }
				if(f_min > 0){
					for(int nod = dest; nod != surs; nod = tata[nod]){
						flux[tata[nod]][nod] += f_min;
						flux[nod][tata[nod]] -= f_min; }
					rez += f_min; } } } }

void add_muc(const int a, const int b, mat<int>& adiac){
	adiac[a].push_back(b);
	adiac[b].push_back(a); }

int main(){
	ifstream f("harta.in");
	ofstream g("harta.out");
	int n;
	f >> n;
	const int surs = 0, outs = 1, ins = n+1, dest = 2*n+1, sz = 2*n+2;
	mat<int> adiac(sz), cap(sz, vector<int>(sz, 0)), flux(sz, vector<int>(sz, 0));
	for(int i = 0; i < n; ++i){
		f >> cap[surs][outs+i] >> cap[ins+i][dest];
		add_muc(surs, outs+i, adiac);
		add_muc(ins+i, dest, adiac); }
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			if(i != j){
				cap[outs+i][ins+j] = 1;
				add_muc(outs+i, ins+j, adiac); } } }
	const int m = flux_max(surs, dest, adiac, cap, flux);
	g << m << '\n';
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			if(flux[i+outs][j+ins] == 1){
				g << i+1 << ' ' << j+1 << '\n'; } } }
	return 0; }