Cod sursa(job #221268)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 15 noiembrie 2008 13:40:22
Problema Taramul Nicaieri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 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;
void print(){
	int i,j;
	for (i=0;i<=2*n+1;++i){
		for (j=0;j<=2*n+1;++j)
			printf("%d ",flux[i][j]);
		printf("\n");
	}
	printf("\n");
	
	for (i=0;i<=2*n+1;++i){
		for (j=0;j<=2*n+1;++j)
			printf("%d ",c[i][j]);
		printf("\n");
	}
	printf("\n");
}
bool bf(){
    int i;
	queue<int> Q;//fprintf(stderr,"\n");
    Q.push(0);//printf("%s ","am intrat in bf");
	//t.resize(2*n+2,-1);
	//print();
	for (i=0;i<=2*n+1;++i)
		t[i]=-1;
	//for (i=0;i<=2*n+1;++i)
		//printf("%d ",t[i]);
	while (!Q.empty()){
		//fprintf(stderr,"%d\n",Q.front());
        for(i=1;i<=2*n+1;++i)
            if (flux[Q.front()][i]<c[Q.front()][i] && t[i]==-1){
                Q.push(i);
                t[i]=Q.front();
                if(i==2*n+1)
                    return true;
            }
        Q.pop();
    }
    return false;
}
int minim(){
    int i=2*n+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=2*n+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(minx);
    }
}
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(2*n+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<=2*n;++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<=2*n;++i)
        c[i][2*n+1]=in[i-n];
    fluxx();
    for (i=1;i<=n;++i)
        for (j=n+1;j<=2*n;++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);
}