Cod sursa(job #3194261)

Utilizator dra_soloSolomon Dragos dra_solo Data 17 ianuarie 2024 14:45:32
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;

#define NMAX 256
vector< int >G[NMAX]; // Un vector de liste de adiacență pentru a reprezenta graful

int N, NODT; // N este numărul de noduri, NODT este nodul țintă în rețea
int C[NMAX][NMAX]; // Matricea de capacități pentru a stoca capacitățile muchiilor grafului
int pred[NMAX+4]; // Vectorul de predecesori pentru reconstruirea căilor

// Funcția Bellman-Ford pentru a găsi o cale de augmentare în rețea
bool bf() {
    vector< int >::iterator it;
    memset(pred, -1, sizeof(pred));
    
    int nod;
    queue < int > Q;
    Q.push(0);
    
    while (!Q.empty()) {
        nod = Q.front();
        if (nod == NODT) break;
        for (it = G[nod].begin(); it != G[nod].end(); ++it) {
            if (pred[*it] == -1 && C[nod][*it] > 0) {
                Q.push(*it);
                pred[*it] = nod;
            }
        }
        Q.pop();
    }
    if (nod != NODT) return 1;
    
    for (nod = NODT; nod; nod = pred[nod]) {
        --C[pred[nod]][nod];
        ++C[nod][pred[nod]];
    }
    
    return 0;
}

// Funcție pentru a afișa rezultatul
void show() {
    int i, j;
    for (i = 1; i <= N; ++i)
        for (j = 1; j <= N; ++j)
            if (i != j && !C[i][j + N]) {
                printf("%d %d\n", i, j);
            }
}

// Funcția care rezolvă problema fluxului maximal
void solve() {
    int ANS = 0;
     
    while (!bf()) {
        ++ANS;
    }
            
    printf("%d\n", ANS);     
    show();
}

int main() {
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);
    
    scanf("%d", &N);
    NODT = (N << 1) + 2;
    
    int i, j;
    int a1, a2;
    for (i = 1; i <= N; ++i) {
        scanf("%d%d\n", &a1, &a2);
             
        G[i].push_back(0);
        G[0].push_back(i);
        C[0][i] = a1;
             
        G[i + N].push_back(NODT);
        G[NODT].push_back(i + N);
        C[i + N][NODT] = a2;
             
        for (j = 1; j <= N; ++j) {
            if (j != i) {
                G[i].push_back(j + N);
                G[j + N].push_back(i);
                C[i][j + N] = 1;
                C[j + N][i] = 0;
            }
        }
    }
    
    solve();    
    return 0;
}