Cod sursa(job #2123648)

Utilizator omegasFilip Ion omegas Data 6 februarie 2018 14:41:18
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

struct graf{
int nod;
graf* next;
};

int n;


graf* g[205];
int res[205][205];

int flow;
int c[205];
int q[205];
int a,b;
int tati[205];
int dist[205];

void add(int a, int b, graf* v[])
{
    graf* q = new graf;
    q->nod  = b;
    q->next = v[a];
    v[a] = q;
}

void addd(int a, int b, graf* v[]){
    add(a,b,v);
    add(b,a,v);
}

void BFS(int k,int d){
    graf*  p;
    for(p = g[k]; p!=NULL; p=p->next){
        if(c[p->nod] == 0 && res[p->nod][k] > 0){
            ++b;
            q[b] = p->nod;
            c[p->nod] = 1;
            dist[p->nod] = d + 1;
        }
    }
    ++a;

    if(b >= a)
        BFS(q[a],dist[q[a]]);
}

void augment(int k){
    int x = k;
    int minim = 100200;

    while(x != 1){
        if(minim > res[tati[x]][x])
            minim = res[tati[x]][x];
        x = tati[x];
    }
    flow = flow + minim;

    x = k;
    while(x != 1){
        res[tati[x]][x] = res[tati[x]][x] - minim;
        res[x][tati[x]] = res[x][tati[x]] + minim;
        x = tati[x];
    }
}

int N;
void print(){
int i,j;
for(i=1;i<=N;++i){
    for(j=1;j<=N;++j)
        cout << res[i][j] << " ";
            cout << "\n";
}
}


int main()
{
    int m,x,y,z,i,j;
    fin >> n ;

    N = 2*n +2;
    for(i=2;i<=n + 1;++i){
        fin >> x >> y ;
        addd(1,i,g);
        addd(i + n,2*n + 2,g);
        res[1][i] = x;
        res[i + n][2*n + 2] = y;
        for(j=2 + n;j<=n + n + 1 ;++j){
            addd(i,j,g);

            res[i][j] = 1;
        }
    }
    for(i = 2, j = n + 2;i<=n + 1;++i,++j)
        res[i][j] = 0;


    c[N] = 1;
    for(i=1;i<=N-1;++i)
        c[i] = 0;
    a = b = 0;
    q[0] = N;

    BFS(N,0);
    int current = 1;
    int aux;
    bool liar = 1;

    while(dist[1] < N){
            graf*  p;
            aux = 1002;
            liar = 1;
            for(p = g[current]; p!=NULL; p=p->next){
                if(dist[p->nod]<aux && res[current][p->nod])
                    aux = dist[p->nod];

                if(dist[p->nod] + 1 == dist[current] && res[current][p->nod]){
                    liar = 0;
                    tati[p->nod] = current;
                    current = p->nod;
                    if(current == N){
                        augment(N);
                        current = 1;
                    }
                    break;
                }
            }

            if(liar){
                dist[current] = aux + 1;
                if(current != 1)
                    current = tati[current];
            }
    }

    fout << flow << "\n";
    for(i = 2;i<=n + 1;++i)
    for(j = n + 2; j <= n + n +1; ++j)
        if(res[i][j] == 0 && i != j - n)
            fout << i - 1 << " " << j-n-1 << "\n";


    return 0;
}