Cod sursa(job #1589202)

Utilizator livliviLivia Magureanu livlivi Data 3 februarie 2016 20:48:40
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<cstdio>
#include<bitset>
#include<queue>
#define N 200
using namespace std;

int c[N+3][N+3];
int f[N+3][N+3];
int tata[N+3];

bitset<N+3> viz;
int m;

int minim(int a,int b){
    return (a<b) ? a : b;
}

bool bfs(){
    int nod,i;

    queue<int> q;
    viz.reset();

    q.push(1);
    viz[1]=true;
    while(!q.empty()){
        nod=q.front();
        q.pop();
        if (nod==m) break ;

        for(i=2;i<=m;i++)
            if (c[nod][i]-f[nod][i]>0 &&viz[i]==false){
                tata[i]=nod;
                viz[i]=true;
                q.push(i);
            }
    }

    return viz[m];
}


void flux(){
    int i,min,nod;

    while(bfs()){
        for(i=1;i<m;i++)
            if (c[i][m]-f[i][m]>0 &&viz[i]==true){
                tata[m]=i;

                min=c[i][m]-f[i][m];
                nod=i;
                while(nod!=1){
                    min=minim(min,c[tata[nod]][nod]-f[tata[nod]][nod]);
                    nod=tata[nod];
                }

                nod=m;
                while(nod!=1){
                    f[tata[nod]][nod]+=min;
                    f[nod][tata[nod]]-=min;
                    nod=tata[nod];
                }
            }
    }
}


int main(){
    freopen ("harta.in","r",stdin);
    freopen ("harta.out","w",stdout);
    int n,i,x,y,j,s=0;

    scanf ("%d",&n);
    m=n*2+2;
    for(i=1;i<=n;i++){
        scanf ("%d%d",&x,&y);
        c[1][i+1]=x;
        c[n+i+1][m]=y;
        s+=x;
    }

    for(i=2;i<=n+1;i++){
        for(j=n+2;j<m;j++)
            c[i][j]=1;
        c[i][n+i]=0;
    }

    flux();

    printf ("%d\n",s);
    for(i=2;i<=n+1;i++)
        for(j=n+2;j<m;j++)
            if (f[i][j]==1) printf ("%d %d\n",i-1,j-n-1);

    return 0;
}