Cod sursa(job #2216912)

Utilizator flibiaVisanu Cristian flibia Data 28 iunie 2018 13:09:08
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <bits/stdc++.h>
#define N 110

using namespace std;

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

int n, IN[N], OUT[N], C[N << 1][N << 1], S, F, dad[N << 1], flow, maxflow;
vector <int> v[N << 1];
queue <int> q;
bool viz[N << 1];

bool bfs(){
	memset(viz, 0, sizeof viz);
	viz[S] = 1;
	q.push(S);
	while(q.size()){
		int from = q.front();
		q.pop();
		if(from == F)
			continue;
		for(auto to : v[from]){
			if(!viz[to] && C[from][to] > 0){
				q.push(to);
				viz[to] = 1;
				dad[to] = from;
			}
		}
	}
	return viz[F];
}

int main(){
	in >> n;
	for(int i = 1; i <= n; i++)
		in >> IN[i] >> OUT[i];
	F = 2 * n + 1;
	for(int i = 1; i <= n; i++){
		v[S].push_back(i);
		v[i].push_back(S);
		v[i + n].push_back(F);
		v[F].push_back(i + n);
		C[S][i] = IN[i];
		C[i + n][F] = OUT[i];
	}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++){
			if(i == j)
				continue;
			v[i].push_back(n + j);
			v[n + j].push_back(i);
			C[i][n + j] = 1;
		}
	while(bfs()){
		maxflow = 123456;
		for(int i = F; i != S; i = dad[i])
			maxflow = min(maxflow, C[dad[i]][i]);
		for(int i = F; i != S; i = dad[i]){
			C[dad[i]][i] -= maxflow;
			C[i][dad[i]] += maxflow;
		}
		flow += maxflow;
	}
	out << flow;
	for(int i = 1; i <= n; i++)	
		for(int j = 1; j <= n; j++)
			if(i != j && !C[i][n + j])
				out << '\n' << i << ' ' << j;
	return 0;
}