Cod sursa(job #1441227)

Utilizator StefanRARapeanu-Andreescu Stefan StefanRA Data 23 mai 2015 22:40:13
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 2.37 kb
#include <fstream>
#include <vector>
#include <queue>

#define MAXN 203

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

int n, x, y, source, destination, roads, previous[MAXN], flow[MAXN][MAXN], capacity[MAXN][MAXN];

std::vector<int> graph[MAXN];
std::queue<int> q;

bool accessible()
{
	int vertex, neighbour;
	unsigned iterator;
	for (iterator=1;iterator<=destination;++iterator)
		previous[iterator]=-1;
	previous[source]=0;
	q.push(source);
	while (!q.empty())
	{
		vertex=q.front();
		q.pop();
		for (iterator=0;iterator<graph[vertex].size();++iterator)
		{
			neighbour=graph[vertex][iterator];
			if (previous[neighbour]==-1 && flow[vertex][neighbour]<capacity[vertex][neighbour])
			{
				previous[neighbour]=vertex;
				q.push(neighbour);
			}
		}
	}
	if (previous[destination]==-1)
		return false;
	return true;
}

void maximum_flow()
{
	int vertex, value;
	unsigned iterator;
	while (accessible())
	{
		for (iterator=0;iterator<graph[destination].size();++iterator)
		{
			vertex=graph[destination][iterator];
			if (flow[vertex][destination]>=capacity[vertex][destination])
				continue;
			value=capacity[vertex][destination]-flow[vertex][destination];
			while (previous[vertex])
			{
				value=std::min(value, capacity[previous[vertex]][vertex]-flow[previous[vertex]][vertex]);
				vertex=previous[vertex];
			}
			roads+=value;
			vertex=graph[destination][iterator];
			flow[vertex][destination]+=value;
			flow[destination][vertex]-=value;
			while (previous[vertex])
			{
				flow[previous[vertex]][vertex]+=value;
				flow[vertex][previous[vertex]]-=value;
				vertex=previous[vertex];
			}
		}
	}
}

int main()
{
	unsigned i, j;
	std::ios_base::sync_with_stdio(false);
	fin>>n;
	for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
		{
			if(i == j)
				continue;
			graph[i].push_back(j+n);
			graph[j+n].push_back(i);
			capacity[i][j+n]=1;
		}
	source=2*n+1;
	destination=2*n+2;
	for(i = 1; i <= n; ++i)
	{
		fin>>x>>y;
		graph[source].push_back(i);
		graph[i].push_back(source);
		capacity[source][i]=x;
		graph[i+n].push_back(destination);
		graph[destination].push_back(i+n);
		capacity[i+n][destination]=y;
	}
	maximum_flow();
	fout<<roads<<'\n';
	for (i=1;i<=n;++i)
		for (j=1;j<=n;++j)
		{
			if (i==j)
				continue;
			if (flow[i][j+n])
				fout<<i<<' '<<j<<'\n';
		}
	return 0;
}