Cod sursa(job #585165)

Utilizator cdascaluDascalu Cristian cdascalu Data 28 aprilie 2011 10:32:18
Problema Taramul Nicaieri Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
#define Nmax 301
#define INF 0x3f3f3f3f
using namespace std;
int N,S,D,C[Nmax][Nmax],F[Nmax][Nmax],T[Nmax];
vector<int> G[Nmax];
queue<int> Q;
bitset<Nmax> viz;
void read()
{
	ifstream f("harta.in");
	f>>N;
	int i,a,b;
	D = 300;
	for(i=1;i<=N;++i)
	{
		f>>a>>b;
		G[0].push_back(i);
		C[0][i] =  a;
		G[i+N].push_back(D);
		C[i+N][D] = b;
		G[D].push_back(i+N);
	}
	f.close();
	int j;
	for(i=1;i<=N;++i)
		for(j=1;j<=N;++j)
			if(i!=j && C[0][i] && C[j+N][D])
			{
				G[i].push_back(j+N);
				G[j+N].push_back(i);
				C[i][j+N] = 1;
			}
}
int bf()
{
	viz.reset();
	Q.push(S);
	int nod;
	while(!Q.empty())
	{
		nod = Q.front();
		Q.pop();
		if(nod == D)continue;
		for(vector<int>::iterator it = G[nod].begin();it!=G[nod].end();++it)
			if(!viz[*it] && C[nod][*it] > F[nod][*it])
			{
				T[*it] = nod;
				viz[*it] = 1;
				Q.push(*it);
			}
	}
	return viz[D];
}
int main()
{
	read();
	int i,r;
	while(bf())
	{
		for(vector<int>::iterator it = G[D].begin();it!=G[D].end();++it)
		if(viz[*it] && C[*it][D] > F[*it][D])
		{
			T[D] = *it;
			i = D;
			r = INF;
			while(i!=S)
			{
				r = min(r,C[T[i]][i] - F[T[i]][i]);
				i = T[i];
			}
			if(r==0)continue;
			i = D;
			while(i!=S)
			{
				F[T[i]][i] += r;
				F[i][T[i]] -= r;
				i = T[i];
			}
		}
	}
	ofstream g("harta.out");
	int j,sol[2][1001],nr=0;
	for(i=1;i<=N;++i)
		for(j=1;j<=N;++j)
			if(F[i][j+N]>0)
			{
				sol[0][++nr] = i;
				sol[1][nr] = j;
			}
	g<<nr<<"\n";
	for(i=1;i<=nr;++i)
		g<<sol[0][i]<<" "<<sol[1][i]<<"\n";
	g.close();
	return 0;
}