Cod sursa(job #562974)

Utilizator katakunaCazacu Alexandru katakuna Data 24 martie 2011 10:08:45
Problema Taramul Nicaieri Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

const char InFile[]="harta.in";
const char OutFile[]="harta.out";
const int MaxN=256;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,x,y,S,D,T[MaxN],F[MaxN][MaxN],C[MaxN][MaxN];
vector<int> A[MaxN];

inline void connect(const int &nod1, const int &nod2, const int &c)
{
	A[nod1].push_back(nod2);
	A[nod2].push_back(nod1);
	C[nod1][nod2]=c;
}

inline int BFS()
{
	int V[MaxN];
	memset(V,0,sizeof(V));
	memset(T,0,sizeof(T));
	
	queue<int> q;
	q.push(S);
	while(!q.empty())
	{
		int nod=q.front();
		q.pop();
		V[nod]=1;
		for(vector<int>::iterator it=A[nod].begin();it!=A[nod].end();++it)
		{
			if(!V[*it] && C[nod][*it]>F[nod][*it])
			{
				T[*it]=nod;
				q.push(*it);
			}
		}
	}
	return T[D];
}

inline int flux()
{
	int flux_maxim=0;
	while(BFS())
	{
		for(vector<int>::iterator it=A[D].begin();it!=A[D].end();++it)
		{
			int nod=*it;
			int minim=C[nod][D]-F[nod][D];
			while(T[nod])
			{
				minim=min(minim,C[T[nod]][nod]-F[T[nod]][nod]);
				nod=T[nod];
			}
			nod=*it;
			F[nod][D]+=minim;
			F[D][nod]-=minim;
			while(T[nod])
			{
				F[T[nod]][nod]+=minim;
				F[nod][T[nod]]-=minim;
				nod=T[nod];
			}
			flux_maxim+=minim;
		}
	}
	return flux_maxim;
}

int main()
{
	fin>>N;
	S=(N<<1)+1;
	D=S+1;
	for(register int i=1;i<=N;++i)
	{
		fin>>x>>y;
		connect(S,i,x);
		connect(i+N,D,y);
	}
	fin.close();
	
	for(register int i=1;i<=N;++i)
	{
		for(register int j=1;j<=N;++j)
		{
			if(i!=j)
			{
				connect(i,j+N,1);
			}
		}
	}
	
	fout<<flux()<<"\n";
	for(register int i=1;i<=N;++i)
	{
		for(register int j=1;j<=N;++j)
		{
			if(i!=j)
			{
				if(C[i][j+N]==F[i][j+N])
				{
					fout<<i<<" "<<j<<"\n";
				}
			}
		}
	}
	fout.close();
	return 0;
}