Cod sursa(job #2961593)

Utilizator R3v1v3RAlexe Paul R3v1v3R Data 6 ianuarie 2023 19:01:12
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
/*
	Am aplicat algoritmul Edmonds-Karp avand complexitatea O(n * m * m):
		-> Parcurg graful prin bfs (cautand lanturi intre 1 si n, retinand si arborele bfs)
		-> ma plimb din parinte in parinte pana ajung la 1 pentru a calcula minimul (locul care imi da bottleneck in lant)
*/

#include <bits/stdc++.h>

using namespace std;

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

int n,m,k;
vector< vector<int > > edges;
int cap[20005][20005];
vector<int> arb;
vector<int> vis;
int maxFlow;

bool bfs(){
	fill(arb.begin(), arb.end(),0);
	fill(vis.begin(), vis.end(),0);
	arb[0] = 0;
	vis[0] = 1;
	queue<int> q;
	q.push(0);
	while(!q.empty()){
		int curr = q.front();
		q.pop();

		if(curr == 2*n+1)
			return true;
		
		for(int i = 0; i < edges[curr].size(); ++i){
			if(vis[edges[curr][i]] == 0 && cap[curr][edges[curr][i]] > 0){
				arb[edges[curr][i]] = curr;
				vis[edges[curr][i]] = 1;
				q.push(edges[curr][i]);
			}
		}
	}
	return false;
}

int main(){
	fin >> n;
	edges.resize(n*2+2);
	arb.resize(n*2+2);
	vis.resize(n*2+2);

	int a,b;

	for(int i = 1; i <= n; ++i){
		fin >> a >> b;
		edges[i].push_back(0);
		edges[0].push_back(i);
		edges[n+i].push_back(2*n+1);
		edges[2*n+1].push_back(n+i);
		cap[0][i] = a;
		cap[i+n][2*n+1] = b;
	}

	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j){
			if(i != j){
				edges[i].push_back(j+n);
				edges[j+n].push_back(i);
				cap[i][n+j] = 1;
			}
		}
	}
	while(bfs()){
		for(int i = 0; i < edges[2*n+1].size(); ++i){
			if(vis[edges[2*n+1][i]] == 1){
				int fl = INT_MAX;
				arb[2*n+1] = edges[2*n+1][i];
				for(int j = 2*n+1; j != 0; j = arb[j]){
					fl = min(fl, cap[arb[j]][j]);
				}
				if(fl != 0){
					for(int j = 2*n+1; j != 0; j = arb[j]){
						cap[arb[j]][j] -= fl;
						cap[j][arb[j]] += fl;
					}
					maxFlow += fl;
				}
			}
		}
	}
	fout << maxFlow << '\n';
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j < edges[i].size(); ++j){
			if(cap[i][edges[i][j]] == 0){
				fout << i  << ' ' << edges[i][j] - n  << '\n';
			}
		}
	}
}