Cod sursa(job #3186343)

Utilizator sebimihMihalache Sebastian sebimih Data 22 decembrie 2023 19:20:28
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <queue>

using namespace std;

const int N = 105;

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

int n, src, dst;
vector<int> g[2 * N];
vector<bool> vizitat;
int capacitate[2 * N][2 * N], flow[2 * N][2 * N], t[2 * N];

void bfs()
{
	vizitat.assign(dst + 1, false);

	queue<int> q;
	q.push(src);
	vizitat[src] = true;
	t[src] = 0;

	while (!q.empty())
	{
		int current = q.front();
		q.pop();

		if (current == dst)
		{
			continue;
		}

		for (int next : g[current])
		{
			if (!vizitat[next] && capacitate[current][next] != flow[current][next])
			{
				vizitat[next] = true;
				t[next] = current;
				q.push(next);
			}
		}
	}
}

int main()
{
	fin >> n;

	src = 0;
	dst = 2 * n + 1;

	int totalMuchii = 0;

	for (int i = 1; i <= n; i++)
	{
		int out, in;
		fin >> out >> in;

		totalMuchii += in;

		capacitate[src][i] = out;
		capacitate[n + i][dst] = in;

		g[src].push_back(i);
		g[i].push_back(src);

		g[n + i].push_back(dst);
		g[dst].push_back(n + i);
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i != j)
			{
				capacitate[i][n + j] = 1;

				g[i].push_back(n + j);
				g[n + j].push_back(i);
			}
		}
	}

	// flux
	while (true)
	{
		bfs();

		if (vizitat[dst] == false)
		{
			break;
		}

		// ia in calcul toate lanturile
		for (int next : g[dst])
		{
			if (vizitat[next] == false || capacitate[next][dst] == flow[next][dst])
			{
				continue;
			}

			t[dst] = next;

			int minFlow = INT_MAX;
			for (int nod = dst; nod != src; nod = t[nod])
			{
				minFlow = min(minFlow, capacitate[t[nod]][nod] - flow[t[nod]][nod]);
			}

			if (minFlow == 0)
			{
				continue;
			}

			for (int nod = dst; nod != src; nod = t[nod])
			{
				flow[t[nod]][nod] += minFlow;
				flow[nod][t[nod]] -= minFlow;
			}
		}
	}

	fout << totalMuchii << '\n';
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i != j && capacitate[i][n + j] == flow[i][n + j])
			{
				fout << i << ' ' << j << '\n';
			}
		}
	}

	return 0;
}

/*

	OBS:
	- impartim in 2 multimi de n elemente
	- conectam primele n varfuri la sursa cu capacitate = muchii_iesire
	- conectam ultimele n varfuri la destinatie cu capacitate = muchii_intrare
	- conectam primele n varfuri la ultimele n varfuri cu capacitate = 1 (nu conectam nodul la el insusi => [i != n + i]) => simulam ce varfuri conectam 
	- aplicam Edmonds-Karp
	
*/