Cod sursa(job #2422443)

Utilizator topala.andreiTopala Andrei topala.andrei Data 18 mai 2019 19:46:44
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <iostream>
#include <fstream>
#include <queue>

#define MAXN 201
#define INF 1<<30
#define DEST 2*N + 1
#define START 0
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<int> G[MAXN];
int C[MAXN][MAXN], F[MAXN][MAXN];
int N, M, father[MAXN];
bool bfs() {
    int node, next;
    bool viz[MAXN] = {false};
    queue<int> Q;

    Q.push(START);
    viz[START] = true;
    while (!Q.empty()) {
        node = Q.front();
        Q.pop();
        for (int i = 0; i < G[node].size(); ++i) {
            next = G[node][i];
            if (viz[next] == false && C[node][next] != F[node][next]) {
                viz[next] = true;
                Q.push(next);
                father[next] = node;
                if (next == DEST) {
                    return true;
                }
            }
        }
    }
    return false;
}
int main()
{
    int x, y, capacity, flux_min;
    int inter, exter;
    f >> N;
    for (int i = 1; i <= N; ++i) {
        f >> exter >> inter;
        C[START][i] = exter;
        C[N + i][DEST] = inter;
        G[START].push_back(i);
        G[i].push_back(START);

        G[DEST].push_back(N + i);
        G[N + i].push_back(DEST);
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = N + 1; j <= 2 * N; ++j) {
            if (j != N + i) {
                C[i][j] = 1;
                G[i].push_back(j);
                G[j].push_back(i);
            }
        }
    }
    int flux = 0;
    while (bfs() == true) {
        flux_min = INF;
        int node = DEST;
        while (node != START) {
            flux_min = min(flux_min, C[father[node]][node] - F[father[node]][node]);
            node = father[node];
        }
        node = DEST;
        while (node != START) {
            F[father[node]][node] += flux_min;
            F[node][father[node]] -= flux_min;
            node = father[node];
        }
        flux += flux_min;
    }
    g << flux << '\n';
    for (int i = 1; i <= N; ++i) {
        for (int j = N + 1; j <= 2 * N; ++j) {
            if (F[i][j] != 0) {
                g << i << ' ' << j - N << '\n';
            }
        }
    }
    return 0;
}