Cod sursa(job #3320965)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 7 noiembrie 2025 19:10:52
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#define ll long long

using namespace std;

const string txt = "data", file = "harta";
const int nmax = 1e5 + 5;

ifstream f(file + ".in");
ofstream g(file + ".out");

int n, flow[205][205], t[205], viz[205];
vector<int> v[205];
vector<pair<int, int>> ans;

bool bfs()
{
	queue<int> q; while (!q.empty()) q.pop();
	q.push(0); fill(viz, viz + 201, 0);
	fill(t, t + 201, 0); viz[0] = 1;

	while (!q.empty())
	{
		int node = q.front(); q.pop();
		for (auto x : v[node]) {
			if (viz[x] || flow[node][x] <= 0) continue;

			viz[x] = 1; t[x] = node; q.push(x);
		}
	}

	return viz[2 * n + 1];
}

void maxflow()
{
	int i = 1;
	while(bfs())
	{
		int sum = 1000;
		for (int i = 2 * n + 1; i != 0; i = t[i])
			sum = min(sum, flow[t[i]][i]);
	
		for (int i = 2 * n + 1; i != 0; i = t[i])
			flow[t[i]][i] -= sum, flow[i][t[i]] += sum;
	}
}

int main()
{
	f >> n;
	for (int i = 1; i <= n; i++)
	{
		f >> flow[0][i] >> flow[i + n][2 * n + 1];
		v[0].push_back(i); v[i].push_back(0);
		v[2 * n + 1].push_back(i + n); 
		v[i + n].push_back(2 * n + 1);
	}

	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= n; j++)
			if (i != j) {
				v[i].push_back(j + n); 
				v[j + n].push_back(i);
				flow[i][j + n] = 1;
			}

	maxflow();

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (i != j && !flow[i][j + n])
				ans.push_back({ i, j });

	g << ans.size() << '\n';
	for (auto x : ans)
		g << x.first << " " << x.second << '\n';
	return 0;
}