Cod sursa(job #887411)

Utilizator vendettaSalajan Razvan vendetta Data 23 februarie 2013 19:08:55
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.58 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("harta.in");
ofstream g("harta.out");

#define nmax 105*2
#define ll long long
#define inf (1<<30)

int n, intra[nmax/2], iese[nmax/2], capac[nmax][nmax], flux[nmax][nmax], t[nmax];
bool viz[nmax];
vector<int> gf[nmax];
int Cnt = 0;
int q[nmax*2];

void citeste(){
    f >> n;
    for(int i=1; i<=n; ++i){
        f >> intra[i] >> iese[i];
        Cnt += intra[i];
    }
}

void bagaS(int S){
    // muchii de genul S - > i de capacitate iese[i]
    for(int i=1; i<=n; ++i){
        if (iese[i] == 0) continue;
        gf[S].push_back(i);
        gf[i].push_back(S);
        capac[S][i] = iese[i];
    }
}

void bagaD(int D){
    // muchii de genul i -> D de capacitate intra[i]
    for(int i=1; i<=n; ++i){
        if (intra[i] == 0) continue;
        int i2 = i + n;
        gf[i2].push_back(D);
        gf[D].push_back(i2);
        capac[i2][D] = intra[i];
    }
}

void faGraf(){
    // pe alea din multimea dreapta le reindexez de la n+1 la n*2;
    for(int i=1; i<=n; ++i){
        if (iese[i] == 0) continue;
        for(int j=1; j<=n; ++j){
            if (i == j || intra[j] == 0) continue;
            int j2 = n+j;
            gf[i].push_back(j2);
            gf[j2].push_back(i);
            capac[i][j2] = 1;
        }
    }

    int S = 0; int D = n*2+1;
    bagaS(S); bagaD(D);
}

inline bool bfs(int S, int D){
    for(int i=0; i<=D; ++i) viz[i] = 0, t[i] = 0;
    int st=1; int dr=0;
    q[++dr] = S; viz[S] = 1;// e marcat

    for(; st<=dr; ){
        int nod = q[st]; ++st;
        for(int i=0; i<gf[nod].size(); ++i){
            int vc = gf[nod][i];
            if (viz[vc] == 0 && capac[nod][vc] > flux[nod][vc]){
                t[vc] = nod;
                viz[vc] = 1;
                q[++dr] = vc;
            }
        }
    }
    return viz[D];
}

void rezolva(){
    // ideea ar fi asa imi formez un graf bipartiti in care intr-o parte am nodurile semnificand nr de muchii ce ies din nod
    // iar in cealalta cele care intra; pot baga un cuplaj maxim; pt a scapa de restrictiile din enunt il fac cu flux
    // astfel mai bag o sursa si o destinatie; bag cate o muchie de la sursa la fiecare nod din multimea stanga
    // doar ca pun capacitatea egala cu muchiile care ies din fiecare nod
    // iar apoi din fiecaren od din multimea dreapta bag o muchie in destinatie cu capacitatea egala cu nr de muchiii ce intra in fiecare nod
    // astfel facand un flux maxim pe graful format imi va da graful cerut
    // iar intre nodurile din multimi bag cate o muchie de capacitate 1;
    faGraf();
    // air acum pe graful asta bag un flux maxim
    int S = 0; int D = 2*n+1;
    for(; bfs(S, D); ){
        int Min = inf;
        for(int i=D; i!=S; i=t[i]){
            // am muchie de genul t[i]->i
            Min = min(Min, capac[ t[i] ][i] - flux[ t[i] ][i]);
        }
        //bag fluxul
        for(int i=D; i!=S; i=t[i]){
            flux[ t[i] ][i] += Min;
            flux[i][ t[i] ] -= Min;
        }
    }

    // muchiile noului graf vor fi acele muchii din graful rezidual care sunt saturate
    //cout << Cnt << "\n";
    g << Cnt << "\n";
    for(int i=1; i<=n; ++i){
        for(int j=n+1; j<=2*n; ++j){
            if (flux[i][j] != 0){
                //cout << j-n << " " << i << "\n";
                g << j-n << " " << i << "\n";
            }
        }
    }
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}