Cod sursa(job #418978)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 16 martie 2010 19:40:15
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<cstdio>
#include<bitset>
#include<queue>
#include<vector>
using namespace std;
#define minn(a,b) ((a<b)?a:b)
#define pb push_back
#define NM 205
#define sh short int
#define OO (1<<30)
vector<sh>a[NM];

bitset<NM>viz;
sh N,c[NM][NM],f[NM][NM],x,y,t[NM],u,nod;
queue<sh>q;
int r,flux;
bool bf()
{
	viz.reset();
	sh S=(N<<1)+2,D=(N<<1)+3;
	viz[S]=1;
	q.push(S);
	++u;
	while (u)
	{
		x=q.front();
		q.pop();
		--u;
		if (x==(N<<1)+3)
			continue;
		size_t g=a[x].size();
		for (size_t i=0; i<g; ++i)
		{
			y=a[x][i];
			if (viz[y]||c[x][y]==f[x][y])
				continue;
			t[y]=x;
			q.push(y);
			viz[y]=1;
			++u;
		}
	}
	return viz[D];
}
int main()
{
	freopen("harta.in","r",stdin);
	freopen("harta.out","w",stdout);
	scanf("%hd",&N);
	sh i,j;sh S=(N<<1)+2,D=(N<<1)+3;
	for (i=1; i<=N; ++i)
	{
		for (j=i-1; j; --j)
		{
			a[i].pb(j+N);
			a[j+N].pb(i);
			c[i][j+N]=1;
		}
		for (j=i+1; j<=N; ++j)
		{
			a[i].pb(j+N);
			a[j+N].pb(i);
			c[i][j+N]=1;
		}
		a[S].pb(i);
		a[i].pb(S);
		a[D].pb(i+N);
		a[i+N].pb(D);
		scanf("%d%d",&x,&y);
		c[S][i]=y;
		c[i+N][D]=x;
	}
	flux=0;
	
	while (bf())
	{
		size_t g=a[D].size();
		for (size_t i=0; i<g; ++i)
		{
			nod=a[D][i];
			if (!viz[nod]||c[nod][D]==f[nod][D])
				continue;
			t[D]=nod;
			r=OO;
			for (j=D; j!=S; j=t[j])
				r=minn(r,c[t[j]][j]-f[t[j]][j]);
			if (!r)
				continue;
			for (j=D; j!=S; j=t[j])
			{
				f[t[j]][j]+=r;
				f[j][t[j]]-=r;
			}
			flux+=r;
		}
	}
	int num=0;
	for (i=1; i<=N; ++i)
		for (j=N+1; j<=(N<<1); ++j)
			if (f[i][j]==1)
				++num;
	printf("%d\n",num);
	for (i=1; i<=N; ++i)
		for (j=N+1; j<=(N<<1); ++j)
			if (f[i][j]==1)
				printf("%hd %hd\n",i,j-N);
	return 0;
}