Cod sursa(job #931080)

Utilizator FayedStratulat Alexandru Fayed Data 27 martie 2013 23:03:55
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <cstdio>
#include <queue>
#include <cstring>
#define NMAX 202
using namespace std;

int C[NMAX][NMAX];
int F[NMAX][NMAX];
int Graf[NMAX][NMAX];
int vizitat[NMAX];
int father[NMAX];
int gradin[NMAX];
int gradext[NMAX];
queue < int > q;
int capacitate_reziduala;
int n,flow,D,S;

inline void citesc(){

    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    scanf("%d",&n);
    for(register int i=1;i<=n;++i)
        scanf("%d%d",&gradin[i],&gradext[i]);
}

bool BFS(){

  memset(vizitat,0,sizeof(vizitat));
    q.push(0);
    vizitat[0] = 1;
    int nod;
    while(!q.empty()){
        nod = q.front();
        q.pop();
        if(nod == D) continue;
        for(register int i=0;i<=D;++i)
                if(Graf[nod][i])
            if(!vizitat[i] && C[nod][i] >F[nod][i]){
                vizitat[i] = 1;
                father[i] = nod;
                q.push(i);
            }
    }
return vizitat[D];
}

inline void Dinic(){

int nod;
    while(BFS())
    for(register int i=n+1;i<D;++i)
       if(vizitat[i] && C[i][D]!=F[i][D]){

        capacitate_reziduala = C[i][D] - F[i][D];
        for(nod = i;nod!=0;nod=father[nod])
            capacitate_reziduala = min(capacitate_reziduala,C[father[nod]][nod] - F[father[nod]][nod]);
        if(capacitate_reziduala){
            flow+=capacitate_reziduala;
            F[i][D]+=capacitate_reziduala;
            F[D][i]-=capacitate_reziduala;

        for(nod = i;nod!=0;nod = father[nod]){
            F[father[nod]][nod]+=capacitate_reziduala;
            F[nod][father[nod]]-=capacitate_reziduala;
        }}
    }
}

inline void solve(){

    for(register int i=1;i<=n;++i)
        for(register int j=n+1;j<=2*n;++j)
            Graf[i][j] = Graf[j][i] = 1 , C[i][j] = 1;

    for(register int i=1;i<=n;++i)
        Graf[i][i+n] = 0;

 S = 0;
 D = 2*n+1;
        for(register int i=1;i<=n;++i){
            Graf[S][i] = Graf[i][S] =1;
            C[S][i] = gradin[i];
            Graf[i+n][D] = Graf[i+n][D] =1;
            C[i+n][D] = gradext[i];
        }
Dinic();
printf("%d\n",flow);
    for(register int i=1;i<=n;++i)
        for(register int j=n+1;j<D;++j)
            if(F[i][j])
                printf("%d %d\n",i,j-n);
}

int main(){

    citesc();
    solve();

return 0;
}