Cod sursa(job #1276200)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 26 noiembrie 2014 01:03:46
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

#define NN 210

queue< pair<int,int> > qq;
struct node{
    int val;
    node *next;
};
node *G[NN],*tmp;
int n , m , x , y , z , i ;
int st[NN] , ant[NN],cap[NN][NN],flux[NN][NN];
bool viz[NN];

void add(int x,int y){
    tmp = new node;
    tmp->val = y;
    tmp->next= G[x];
    G[x] = tmp;
}

bool bfs(){
    st[0] = 1;  st[1] = 0;
    memset( viz , NULL , sizeof(viz) );
    for( i = 1; i <= st[0] ; ++i ){
        x = st[i];
        if( x == m ) continue;
        for( tmp = G[ x]; tmp ; tmp = tmp->next ){
            y = tmp->val;
            if( cap[x][y] == flux[x][y] || viz[y] ) continue;
            viz[y] = true;
            ant[y] = x;
            st[ ++st[0] ] = y;
        }
    }
    return viz[m];
}

int main()
{
    freopen("harta.in" , "r", stdin);
    freopen("harta.out", "w", stdout);
    scanf("%d",&n);
    m =2*n + 1;
    for(i=1;i<=n;++i){
        scanf("%d %d",&x,&y);
        add( 0 , i );
        add( i , 0 );
        cap[0  ][i] = x;
        cap[i+n][m] = y;
        add(i+n,m);
        add(m,i+n);
        for(int j=1;j<=n;++j){
            if( i == j ) continue;
            add(i,j+n);
            add(j+n,i);
            cap[i][j+n] = 1;
        }
        //cap[x][y] += z;
    }
    int flow,fmin;
    while( bfs() )
        for(tmp=G[m] ; tmp ; tmp = tmp->next ){
            x = tmp->val;
            if( flux[x][m] == cap[x][m] || !viz[x] ) continue;
            ant[m] = x;
            fmin = 1 << 30;
            for(x=m; x; x= ant[x] )
                fmin = min(fmin , cap[ ant[x] ][x] - flux[ ant[x] ][x] );
            if( fmin == 0 ) continue;
            for(x=m; x; x= ant[x]){
                flux[ ant[x] ][x] += fmin;
                flux[x][ ant[x] ] -= fmin;
            }
            //flow += fmin;
        }
    //printf("%d",flow);
    for(i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if( i == j ) continue;
            if( flux[i][j+n] == 1 )
            qq.push( {i,j} );
        }
    }
    int tt= qq.size();
  printf("%d\n",tt);
  for( ; tt ; tt-- ){
    printf("%d %d\n",qq.front().first,qq.front().second);
    qq.pop();
  }

    return 0;
}