Cod sursa(job #3193716)

Utilizator DenisaCrCranganu Denisa Mariana DenisaCr Data 15 ianuarie 2024 15:14:26
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n, src, dst;
vector<int>G[2*N];
vector<bool>vizitat;

ifstream f("harta.in");
ofstream g("harta.out");
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()
{
    f >> n;
	src=0;
	dst=2*n+1;
	int totalMuchii = 0;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		f >> x >> y;
		totalMuchii+=y;
		capacitate[src][i]=x;
		capacitate[n+i][dst]=y;
		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);
			}
		}
	}
	while(1)
	{
		bfs();
		if(vizitat[dst]==false) break;
		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;
			}
		}
	}
	g << totalMuchii;
	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])
				g << i << " " << j <<endl;
		}
	}
	return 0;
}