Cod sursa(job #3191372)

Utilizator MarutBrabete Marius Stelian Marut Data 9 ianuarie 2024 16:05:02
Problema Taramul Nicaieri Scor 100
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>viz;
int capacity[2*N][2*N],flow[2*N][2*N],t[2*N];
void bfs()
{
	viz.assign(dst + 1, false);
	queue<int> q;
	q.push(src);
	viz[src]=true;
	t[src]=0;
	while(!q.empty())
	{
		int current=q.front();
		q.pop();
		if(current == dst)
			continue;
		for(int next:G[current])
		{
			if(!viz[next] && capacity[current][next]!=flow[current][next])
			{
				viz[next]=true;
				t[next]=current;
				q.push(next);
			}
		}
	}
}
int main()
{
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    scanf("%d",&n);
	src=0;
	dst=2*n+1;
	int totalMuchii = 0;
	for(int i=1;i<=n;i++)
	{
		int out,in;
		scanf("%d%d",&out,&in);
		totalMuchii+=in;
		capacity[src][i]=out;
		capacity[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)
			{
				capacity[i][n+j]=1;
				G[i].push_back(n+j);
				G[n+j].push_back(i);
			}
		}
	}
	while(1)
	{
		bfs();
		if(viz[dst]==false) break;
		for(int next:G[dst])
		{
			if(viz[next]==false || capacity[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,capacity[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;
			}
		}
	}
	printf("%d\n",totalMuchii);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j && capacity[i][n + j]==flow[i][n + j])
				printf("%d %d\n",i,j);
		}
	}
	return 0;
}