Cod sursa(job #534460)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 15 februarie 2011 19:12:10
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");

#include <vector>
#include <queue>
#define oo 200000000
#define maxn 256
#define pb push_back

int i,j,N,s,d,k,R,flmin;
int C[maxn][maxn],from[maxn],v[maxn];
vector <short> A[maxn];
queue <short> Q;

inline int min(int a, int b)
{
	return a<b ? a : b;
}

void citire()
{
	int x,y;
	fin >> N;
	s=0; d=2*N+1;
	for(i=1;i<=N;i++)
	{
		fin >> x >> y;
		A[s].pb(i);	C[s][i]=x;
		A[i+N].pb(d); C[i+N][d]=y;
		for(j=N+1;j<d;j++)
			if(j!=i+N)
			{
				A[i].pb(j);
				A[j].pb(i);
				C[i][j]=1;
			}
	}
}

int BFS()
{
	for(i=1;i<=d;i++) v[i]=0;
	for(;!Q.empty();Q.pop());
	Q.push(s); v[s]=1;
	for(;!Q.empty();Q.pop())
	{
		k=Q.front();
		for(i=0;i<(int)A[k].size();i++)
			if(C[k][A[k][i]]>0 && !v[A[k][i]])
			{
				from[A[k][i]]=k;
				if(A[k][i]==d) return 1;
				Q.push(A[k][i]);
				v[A[k][i]]=1;
			}
	}
	return 0;
}

int main()
{
	citire();
	while( BFS() )
	{
		flmin=oo;
		for(k=d;k!=s;k=from[k])
			flmin=min(flmin,C[from[k]][k]);
		for(k=d;k!=s;k=from[k])
		{
			C[from[k]][k]-=flmin;
			C[k][from[k]]+=flmin;
		}
		R+=flmin;
	}
	fout << R << '\n';
	for(i=1;i<=N;i++)
		for(j=0;j<(int)A[i].size();j++)
			if(C[i][A[i][j]]==0 && A[i][j]>N)
				fout << i << ' ' << A[i][j]-N << '\n';
}