Cod sursa(job #1714239)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 7 iunie 2016 20:08:47
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
using namespace std;
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define Nmax 210
#define INF 2000000000

int n, sum, S, T;
int f[Nmax][Nmax], c[Nmax][Nmax], pred[Nmax];
vector< int > G[Nmax];
vector< bool > vis(Nmax);
queue< int > Q;

void read();
void compute_flow();
void write();
bool BFS();
void edge(int, int);

int main()
{
	read();

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (i != j)
				c[i][n + j] = 1,
				edge(i, n + j);

	compute_flow();

	write();

    return 0;
}

void read()
{
	int i, din, dout;
	ifstream fin("harta.in");

	fin >> n;
	
	S = 0; T = 2 * n + 1;
	for (i = 1; i <= n; ++i)
	{
		fin >> dout >> din;
		sum += din;

		edge(S, i);
		c[S][i] = dout;

		edge(n + i, T);
		c[n + i][T] = din;
	}

	fin.close();
}

void compute_flow()
{
	int v, minF;

	while (BFS())
	{
		for (auto node : G[T])
		{
			pred[T] = node;

			for (minF = INF, v = T; v != S; v = pred[v])
				if (c[pred[v]][v] - f[pred[v]][v] < minF)
					minF = c[pred[v]][v] - f[pred[v]][v];

			if (minF)
			{
				for (v = T; v != S; v = pred[v])
					f[pred[v]][v] += minF,
					f[v][pred[v]] -= minF;
			}
		}
	}
}

void write()
{
	ofstream fout("harta.out");

	fout << sum << '\n';
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			if (f[i][n + j])
				fout << i << ' ' << j << '\n';

	fout.close();
}

bool BFS()
{
	int v;
	fill(vis.begin(), vis.end(), false);

	for (Q.push(S), vis[S] = true; !Q.empty(); Q.pop())
	{
		v = Q.front();
		if (v == T) continue;

		for (auto &to : G[v])
			if (!vis[to] && c[v][to] > f[v][to])
			{
				pred[to] = v;

				Q.push(to);
				vis[to] = true;
			}
	}

	return vis[T];
}

void edge(int a, int b)
{
	G[a].push_back(b);
	G[b].push_back(a);
}