Cod sursa(job #2579629)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 12 martie 2020 18:04:34
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>

using namespace std;

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

const int INF = 0x3f3f3f3f;

int n;
int flo[214][214], cap[214][214];
vector<int> gra[214];

int edg = 0;

void nuke(){
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			if(i != j){
				cap[i][j+n] = 1;
			}
		}
	}
	for(int i = 1; i <= n; ++i){
		gra[0].push_back(i);
		gra[i].push_back(0);
		gra[2*n+1].push_back(i+n);
		gra[i+n].push_back(2*n+1);
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			if(i != j){
				gra[i].push_back(j+n);
				gra[j+n].push_back(i);
			}
		}
	}
}

void read(){
	fin >> n;
	nuke();
	for(int i = 1; i <= n; ++i){
		int pin, pout;
		fin >> pout >> pin;
		cap[0][i] = pin;
		cap[i+n][2*n+1] = pout;
		edg += pin;
	}
}

queue<int> qu;
bitset<214> vi;
int dad[214];
bool bfs(){
	vi.reset();
	qu.push(0);
	vi[0] = true;
	while(!qu.empty()){
		int a = qu.front();
		qu.pop();
		if(a == 2*n+1)continue;
		for(auto b : gra[a]){
			if(vi[b] || flo[a][b] == cap[a][b])continue;
			vi[b] = true;
			if(b != 2*n+1)qu.push(b);
			dad[b] = a;
		}
	}
	return vi[2*n+1];
}

void solve(){
	while(bfs()){
		for(auto a : gra[2*n+1]){
			if(!vi[a] || flo[a][2*n+1] == cap[a][2*n+1])continue;
			
			int fmin = INF;
			dad[2*n+1] = a;
			for(int x = 2*n+1; x > 0; x = dad[x]){
				fmin = min(fmin, cap[dad[x]][x] - flo[dad[x]][x]);
			}
			
			if(fmin == 0)continue;
			for(int x = 2*n+1; x > 0; x = dad[x]){
				flo[dad[x]][x] += fmin;
				flo[x][dad[x]] -= fmin;
			}
		}
	}
}

void write(){
	fout << edg << "\n";
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			if(flo[i][j+n] == 1){
				fout << i << " " << j << "\n";
			}
		}
	}
}

int main(){
	read();
	solve();
	write();
	return 0;
}