Cod sursa(job #1172040)

Utilizator Kira96Denis Mita Kira96 Data 16 aprilie 2014 18:10:16
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<fstream>
#define pb push_back
#include<iomanip>
#include<cmath>
#include<queue>
#include<cstring>
#define N 220
#define FOR(a,b,c) for(int a=b;a<=c;++a)
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<int> v[N];
queue<int> q;
int viz[N],n,m,F[N][N],C[N][N],T[N],a,x,y,des,nod,mi,t,st[N*N*N],dr[N*N*N];
int bfs(int x)
{
	memset(viz,0,sizeof(viz));
	q.push(0);
	while(!q.empty())
	{
		nod=q.front();
		q.pop();
		if(nod==m)
			continue;
		FOR(i,0,v[nod].size()-1)
		{
			des=v[nod][i];
			if(C[nod][des]==F[nod][des]||viz[des])
				continue;
			T[des]=nod;
			viz[des]=1;
			q.push(des);
		}
	}
	return viz[m];
}
int main ()
{
	f>>n;
	m=2*n+1;
	FOR(i,1,n)
	{
		f>>x>>y;
		C[0][i]=x;
		C[i+n][m]=y;
		v[0].pb(i);
		v[i].pb(0);
		v[i+n].pb(m);
		v[m].pb(i+n);
		
		FOR(j,1,n)
		{
			if(i==j)
				continue;
			v[i].pb(j+n);
			v[j+n].pb(i);
			C[i][j+n]=1;
		}
	}
	while(bfs(0))
	{
		FOR(i,0,v[m].size()-1)
		{
			if(!viz[v[m][i]]||C[v[m][i]][m]==F[v[m][i]][m])
				continue;
			
			T[m]=v[m][i];
			a=m;
			mi=(1<<30);
			for(;a;a=T[a])
				mi=min(mi,C[T[a]][a]-F[T[a]][a]);
			a=m;
			if(mi)
			for(;a;a=T[a])
			{
				F[T[a]][a]+=mi;
				F[a][T[a]]-=mi;
			}
		}
	}
	FOR(i,1,n)
	FOR(j,1,n)
	{
		if(i==j)
			continue;
		if(F[i][j+n]==1)
		{
			st[++t]=i;
			dr[t]=j;
		}
	}
	g<<t<<"\n";
	FOR(i,1,t)
	g<<st[i]<<" "<<dr[i]<<"\n";
	return 0;
}