Cod sursa(job #3329904)

Utilizator flaviussteffflavius stefan flaviussteff Data 16 decembrie 2025 13:03:56
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
struct Muchie {
    int v, cap, flux, rev;
};
vector<Muchie> G[300];
int tata[300];
int id[300];
int N, S, D;
void add(int x, int y, int cap) {
    Muchie a = {y, cap, 0, (int)G[y].size()};
    Muchie b = {x, 0, 0, (int)G[x].size()};
    G[x].push_back(a);
    G[y].push_back(b);
}
bool bfs() {
    fill(tata, tata + D + 1, -1);
    queue<int> Q;
    Q.push(S);
    tata[S] = -2;
    while(!Q.empty()){
        int nod = Q.front();
        Q.pop();

        for(int i = 0; i < G[nod].size(); i++){
            Muchie &m = G[nod][i];
            if(tata[m.v] == -1 && m.cap - m.flux > 0){
                tata[m.v] = nod;
                id[m.v] = i;
                Q.push(m.v);
                if(m.v == D) return true;
            }
        }
    }
    return false;
}
int main() {
    fin >> N;
    S = 0;
    D = 2 * N + 1;
    int total_drumuri = 0;
    for(int i = 1; i <= N; i++) {
        int out, in;
        fin >> out >> in;
        add(S, i, out);
        add(N + i, D, in);
        total_drumuri += out;
    }
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            if(i != j) {
                add(i, N + j, 1);
            }
        }
    }
    while(bfs()) {
        int nod = D;
        while(nod != S) {
            int prev = tata[nod];
            int idx = id[nod];
            G[prev][idx].flux++;
            int rev = G[prev][idx].rev;
            G[nod][rev].flux--;
            nod = prev;
        }
    }
    fout << total_drumuri << "\n";
    for(int i = 1; i <= N; i++) {
        for(int k = 0; k < G[i].size(); k++) {
            if(G[i][k].v > N && G[i][k].v <= 2 * N && G[i][k].flux == 1) {
                fout << i << " " << G[i][k].v - N << "\n";
            }
        }
    }

    return 0;
}