Cod sursa(job #562524)

Utilizator ChallengeMurtaza Alexandru Challenge Data 23 martie 2011 11:20:34
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <list>
#include <queue>
#include <cstring>

using namespace std;

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

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

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

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

inline int flux()
{
	int maxflow=0;
	while(BFS())
	{
		for(list<int>::iterator it=A[D].begin();it!=A[D].end();++it)
		{
			int nod=*it;
			int minim=C[nod][D]-F[nod][D];
			while(nod!=9 && nod!=0)
			{
				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(nod!=9 && nod!=0)
			{
				F[T[nod]][nod]+=minim;
				F[nod][T[nod]]-=minim;
				nod=T[nod];
			}
			maxflow+=minim;
		}
	}
	return maxflow;
}

int main()
{
	fin>>N;
	S=(N<<1)+1;
	D=S+1;
	for(register int i=1;i<=N;++i)
	{
		for(register int j=1;j<=N;++j)
		{
			if(i!=j)
			{
				A[i].push_back(j+N);
				A[j+N].push_back(i);
				C[i][j+N]=1;
			}
		}
	}
	for(register int i=1;i<=N;++i)
	{
		fin>>x>>y;
		int nod2=i+N;
		A[S].push_back(i);
		A[i].push_back(S);
		A[nod2].push_back(D);
		A[D].push_back(nod2);
		C[S][i]=x;
		C[nod2][D]=y;
	}
	fin.close();
	
	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;
}