Cod sursa(job #2962759)

Utilizator NFJJuniorIancu Ivasciuc NFJJunior Data 9 ianuarie 2023 08:13:04
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
#define cin f
#define cout g

//	the matrix capacity stores the residual network capacity
int n;
vector<int> parent;
vector<unordered_map<int, int>> capacity;
vector<unordered_map<int, int>> adj;

bool bfs(int s, int t)
{
	fill(parent.begin(), parent.end(), -1);
	parent[s] = -2;

	queue<int> Q;
	Q.push(s);

	while(! Q.empty())
	{
		int cur = Q.front();
		Q.pop();

		for(auto &edge : capacity[cur])
		{
			if(parent[edge.first] == -1 and edge.second != 0)
			{
				parent[edge.first] = cur;

				if(edge.first == t)
					return true;

				Q.push(edge.first);
			}
		}
	}

	return false;
}

int maxflow(int s, int t)
{
	int flow = 0;

	while(bfs(s, t))
	{
		for(auto &edge : capacity[t])
		{
			int cur = edge.first;
			if(capacity[cur][t] == 0 || parent[cur] == -1)
				continue;

			int new_flow = INT_MAX;
			new_flow = min(new_flow, capacity[cur][t]);

			while(cur != s)
			{
				int prev = parent[cur];
				new_flow = min(new_flow, capacity[prev][cur]);
				if(new_flow == 0)
					break;
				cur = prev;
			}

			if(new_flow == 0)
				continue;
			flow += new_flow;

			cur = edge.first;
			capacity[cur][t] -= new_flow;
			capacity[t][cur] += new_flow;

			while(cur != s)
			{
				int prev = parent[cur];
				capacity[prev][cur] -= new_flow;
				capacity[cur][prev] += new_flow;
				cur = prev;
			}
		}
	}

	return flow;
}

int main()
{
	cin >> n;
	parent.resize(n * 2 + 3);
	capacity.resize(n * 2 + 3);
	adj.resize(n * 2 + 3);
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(i != j)
			{
				adj[i][j + n] = 1;
				capacity[i][j + n] = 1; 
				capacity[j + n][i] = 0;
			}

	int s, t;
	s = n * 2 + 1, t = n * 2 + 2;

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

		adj[s][i] = in;
		capacity[s][i] = in;
		capacity[i][s] = 0;

		adj[i + n][t] = out;
		capacity[i + n][t] = out;
		capacity[t][i + n] = 0;
	}

	cout<<maxflow(s, t)<<'\n';

	for(int i = 1; i <= n; i++)
		for(auto it : adj[i])
			if(capacity[i][it.first] == 0)
				cout<<i<<' '<<it.first - n<<'\n';

	return 0;
}