Cod sursa(job #761399)

Utilizator ioanabIoana Bica ioanab Data 25 iunie 2012 20:43:07
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

ifstream in("harta.in");
ofstream out("harta.out");

const int N=206;

int c[N][N],f[N][N],pred[N],n;
bool use[N];
vector <int> v[N];

bool bfs()
{
	int x;
	
	memset(use,false, sizeof(use));
	memset(pred,0, sizeof(pred));
	
	queue<int> q;
	q.push(0);
	use[0]=true;
	pred[0]=-1;
	
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		for(vector <int> :: iterator it=v[x].begin(); it!=v[x].end();it++)
		{
			if(!use[*it] && c[x][*it]-f[x][*it]>0)
			{
				use[*it]=1;
				pred[*it]=x;
				q.push(*it);
				
				if(*it==2*n+1)
					return true;
			}
		}
	}
	
	return false;
}

int calcmin(int x)
{
	int min=c[x][2*n+1]-f[x][2*n+1];
	while(pred[x]!=-1)
	{
		if(c[pred[x]][x]-f[pred[x]][x]<min)
			min=c[pred[x]][x]-f[pred[x]][x];
		x=pred[x];
	}
	return min;
}

void flux()
{
	int flux,x,mm;
	
	while(bfs())
	{
		for(vector<int> :: iterator it=v[2*n+1].begin();it!=v[2*n+1].end();it++)
		{
			if(use[*it] && c[*it][2*n+1]>f[*it][2*n+1])
			{
				mm=calcmin(*it);
				
				f[*it][2*n+1]+=mm;
				f[2*n+1][*it]-=mm;
				
				x=*it;
				while(pred[x]!=-1)
				{
					f[pred[x]][x]+=mm;
					f[x][pred[x]]-=mm;
					x=pred[x];
				}
			}
		}
	}
}
		
int main()
{
	int i,j,x,y,nr=0;
	in>>n;
	for(i=1;i<=n;i++)
	{
		in>>x>>y;
		
		v[0].push_back(i);
		v[i].push_back(0);
		v[i+n].push_back(2*n+1);
		v[2*n+1].push_back(i+n);
		
		c[0][i]=x;
		c[n+i][2*n+1]=y;
		nr+=x;
	}
	
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j)
			{
				v[i].push_back(n+j);
				v[n+j].push_back(i);
				c[i][n+j]=1;
			}
	
	flux();
	
	out<<nr<<"\n";
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j && f[i][j+n])
				out<<i<<" "<<j<<"\n";
			
	
	return 0;
}