Cod sursa(job #916817)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 16 martie 2013 21:56:22
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <fstream>
#include <queue>
#include <cstring>

#define MAX 205

using namespace std;

int N, S, D, rez;
int C[MAX][MAX], F[MAX][MAX], dad[MAX];
bool viz[MAX];
vector<int> V[MAX];

void citire() {
    ifstream in("harta.in");
    in>>N;
    S = 0, D = 2 * N + 1;
    for(int i = 1, I, O; i <= N; i++) {
        in>>I>>O;
        C[S][i] = I;
        C[i + N][D] = O;
        V[S].push_back(i);
        V[i].push_back(S);
        V[i + N].push_back(D);
        V[D].push_back(i + N);
        for(int j = 1; j <= N; j++) {
            if(i == j) continue;
            V[i].push_back(j + N);
            V[j + N].push_back(i);
            C[i][j + N] = 1;
        }
    } in.close();
}

bool bfs() {
    queue<int> Q;
    memset(viz, 0, sizeof(viz));
    memset(dad, 0, sizeof(dad));
    Q.push(S); viz[S] = true;
    while(!Q.empty()) {
        int nod = Q.front(); Q.pop();
        if(nod == D) continue;
        for(size_t i = 0; i < V[nod].size(); i++) {
            int dest = V[nod][i];
            if(F[nod][dest] == C[nod][dest] || viz[dest]) continue;
            Q.push(dest);
            dad[dest] = nod;
            viz[dest] = true;
        }
    }
    return viz[D];
}

void flux() {
    while(bfs()) {
        for(size_t i = 0; i < V[D].size(); i++) {
            int nod = V[D][i];
            if(F[nod][D] == C[nod][D] || !viz[nod]) continue;
            dad[D] = nod;
            nod = D;
            while(nod != S) {
                F[dad[nod]][nod]++;
                F[nod][dad[nod]]--;
                nod = dad[nod];
            } rez++;
        }
    }
}

void afisare() {
    ofstream out("harta.out");
    out<<rez<<"\n";
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
            if(F[i][j + N])
                out<<i<<" "<<j<<"\n";
    out.close();
}

int main() {
    citire();
    flux();
    afisare();
    return 0;
}