Cod sursa(job #221270)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 15 noiembrie 2008 13:46:37
Problema Taramul Nicaieri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#define N 120
#define oo 19383934
using namespace std;
vector<int> in,out;
int c[2*N][2*N],flux[2*N][2*N];
vector<int> t;
int n;
bool bf(){
    int i;
	queue<int> Q;//fprintf(stderr,"\n");
    Q.push(0);//printf("%s ","am intrat in bf");
	//t.resize((n<<1)+2,-1);
	//print();
	for (i=0;i<=(n<<1)+1;++i)
		t[i]=-1;
	//for (i=0;i<=(n<<1)+1;++i)
		//printf("%d ",t[i]);
	while (!Q.empty()){
		//fprintf(stderr,"%d\n",Q.front());
        for(i=1;i<=(n<<1)+1;++i)
            if (flux[Q.front()][i]<c[Q.front()][i] && t[i]==-1){
                Q.push(i);
                t[i]=Q.front();
                if(i==(n<<1)+1)
                    return true;
            }
        Q.pop();
    }
    return false;
}
int minim(){
    int i=n<<1+1,m=oo;
	//printf("\n***\n");
    while(i){
		//printf("j=%d ",i);
        if(c[t[i]][i]-flux[t[i]][i]<m)
            m=c[t[i]][i]-flux[t[i]][i];
		//printf("(%d,%d) ",t[i],i);
        i=t[i];
    }
    return m;
}

void update(int dif){
    int i=(n<<1)+1;
    while(i){
        flux[t[i]][i]+=dif;
        flux[i][t[i]]-=dif;
		i=t[i];
		//printf("i=%d ",i);
    }
}

void fluxx(){
    int i,j,minx=oo;
    while (bf()){
        //minx=minim();
        update(1);
    }
}
vector< pair<int,int> > sol;
main(){
    int i,j;
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    scanf("%d",&n);
    in.resize(n+1);
    out.resize(n+1);
    t.resize((n<<1)+3,-1);
    for (i=1;i<=n;++i)
        scanf("%d%d",&out[i],&in[i]);
    for (i=1;i<=n;++i)
		for (j=n+1;j<=(n<<1);++j)
			if (j!=i+n)
				c[i][j]=1;
	for (i=1;i<=n;++i)
        c[0][i]=out[i];
    for (i=n+1;i<=(n<<1);++i)
        c[i][(n<<1)+1]=in[i-n];
    fluxx();
    for (i=1;i<=n;++i)
        for (j=n+1;j<=(n<<1);++j)
            if (flux[i][j]==1)
                sol.push_back(make_pair(i,j-n));
    printf("%d\n",sol.size());
    for (i=0;i<sol.size();++i)
        printf("%d %d\n",sol[i].first,sol[i].second);
}