Cod sursa(job #221246)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 15 noiembrie 2008 12:27:10
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#define N 120
#define oo 19383934
using namespace std;
vector<int> in,out;
queue<int> Q;
int c[2*N][2*N],flux[2*N][2*N];
vector<int> t;
int n;
bool bf(){
    int i;
    Q.push(0);
    t.resize(2*n+1,-1);
    while (!Q.empty()){
        for(i=1;i<=2*n;++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;
    while(i){
        if(c[t[i]][i]-flux[t[i]][i]<m)
            m=c[t[i]][i]-flux[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;
    }
}

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)
        c[0][i]=out[i];
    for (i=n+1;i<=2*n;++i)
        c[i][2*n+1]=in[i];
    fluxx();
    for (i=1;i<=n;++i)
        for (j=n+1;j<=2*n;++j);
            if (c[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);
}