Cod sursa(job #2956156)

Utilizator tudorcomanTudor Coman tudorcoman Data 18 decembrie 2022 16:52:53
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.75 kb

#include <fstream>
#include <queue>

using namespace std;

const int maxN = 256; 
const int infi = 1 << 30;

struct Muchie {
    int src, dest;
    int flx, cap; 
    Muchie (int _src = 0, int _dest = 0, int _flx = 0, int _cap = 0):
        src(_src), dest(_dest), flx(_flx), cap(_cap) { }
} father[maxN];

vector<Muchie> G[maxN];
int cost[maxN];

bool bfs(int N) {
    for (int i = 0; i <= 2 * N + 1; i ++) {
        cost[i] = infi;
        father[i] = Muchie(-1);
    }
    queue<int> q;
    cost[0] = 0; q.push(0);
    while(!q.empty()) {
        int top = q.front(); q.pop();
        for (auto it: G[top]) {
            if (cost[top] + 1 < cost[it.dest] && it.flx < it.cap) {
                cost[it.dest] = cost[top] + 1;
                father[it.dest] = it; 
                q.push(it.dest); 
            }
        }
    }
    return cost[2 * N + 1] != infi; 
}


int main() {
    ifstream in("harta.in");
    ofstream out("harta.out");
    int N;
    in >> N; 

    for (int i = 1; i <= N; i ++) {
        int gr_int, gr_ext;
        in >> gr_ext >> gr_int;
        
        G[0].push_back(Muchie(0, i, 0, gr_ext));
        G[i].push_back(Muchie(i, 0, 0, 0));

        G[i + N].push_back(Muchie(i + N, 2 * N + 1, 0, gr_int));
        G[2 * N + 1].push_back(Muchie(2 * N + 1, i + N, 0, 0));
    }

    for (int i = 1; i <= N; i ++) {
        for (int j = N + 1; j <= 2 * N; j ++) {
            if (i + N != j) {
                G[i].push_back(Muchie(i, j, 0, 1));
                G[j].push_back(Muchie(j, i, 0, 0));
            }
        }
    }

    vector<Muchie> drum;
    while(bfs(N)) {
        drum.clear();
        int x = 2 * N + 1;
        while(father[x].src != -1) {
            drum.push_back(father[x]);
            x = father[x].src; 
        }

        int max_flow = infi;
        for (auto it: drum)
            max_flow = min(max_flow, it.cap - it.flx);

        for (auto edge: drum) {
            bool found = false;

            for (int i = 0; i < G[edge.src].size() && !found; i ++) {
                if (G[edge.src][i].dest == edge.dest) {
                    G[edge.src][i].flx += max_flow;
                    found = true;
                }
            }

            found = false;
            for (int i = 0; i < G[edge.dest].size() && !found; i ++) {
                if (G[edge.dest][i].dest == edge.src) {
                    G[edge.dest][i].flx -= max_flow; 
                    found = true;
                }
            }
        }
    }

    int flux = 0;
    for (auto it: G[0])
        flux += it.flx;

    out << flux << '\n';

    for (int i = 1; i <= N; i ++) {
        for (auto it: G[i]) {
            if (it.flx == it.cap && it.dest > N && it.flx != 0) {
                out << it.src << ' ' << it.dest - N << '\n';
            }
        }
    }

    return 0;
}