Cod sursa(job #418666)

Utilizator hadesgamesTache Alexandru hadesgames Data 16 martie 2010 11:05:02
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
vector <int> succ[210];
int n,f,coada[210],tat[210],cap[210][210],fl[210][210],viz[210];
const int inf=1<<30;

int flux()
{
    memset(coada,0,sizeof(coada));
    memset(tat,0,sizeof(tat));
	memset(viz,0,sizeof(viz));
    int r=1,p,minim;
    for (p=1;p<=r;++p)
        for (int i=0;i<succ[coada[p]].size();++i)
        {
            int nod=succ[coada[p]][i];
            if (!viz[nod]&&cap[coada[p]][nod])
            {
                tat[nod]=coada[p];
                coada[++r]=nod;
				viz[nod]=1;
            }
        }
    if (!tat[2*n+1])
        return 0;
	int i=2*n+1;
	minim=inf;
	while (i)
	{
		if (minim>cap[tat[i]][i])
			minim=cap[tat[i]][i];
		i=tat[i];
	}
	i=2*n+1;
	while (i)
	{
		cap[tat[i]][i]-=minim;
		cap[i][tat[i]]+=minim;
		fl[tat[i]][i]+=minim;
		fl[i][tat[i]]-=minim;
		i=tat[i];
	}
	f+=minim;
    return 1;
}

int main()
{
    freopen ("harta.in","r",stdin);
    freopen ("harta.out","w",stdout);
    scanf("%d",&n);
    int x,y;
    for (int i=1;i<=n;++i)
    {
        scanf("%d%d",&x,&y);
        cap[n+i][2*n+1]=y;
        cap[0][i]=x;
        for (int j=1;j<=n;++j)
            if (i!=j)
            {
                cap[i][n+j]=1;
                succ[i].push_back(n+j);
                succ[n+j].push_back(i);
            }
        succ[0].push_back(i);
        succ[i].push_back(0);
        succ[n+i].push_back(2*n+1);
        succ[2*n+1].push_back(n+i);
    }
    while (flux());
    printf("%d\n",f);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            if (i!=j&&fl[i][n+j])
                printf("%d %d\n",i,j);
    return 0;
}