Cod sursa(job #1424973)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 26 aprilie 2015 08:02:51
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

#define inf 0x3f3f3f3f
#define Nmax 300
#define offset 150
#define source 0
#define destination 299

std::ifstream in("harta.in");
std::ofstream out("harta.out");

std::vector<int> G[Nmax];
int F[Nmax][Nmax], C[Nmax][Nmax], T[Nmax];

bool BFS() {
    std::queue<int> Q;
    bool checked[Nmax];
    memset(checked, false, Nmax);

    Q.push(source);
    while (!Q.empty()) {
        int node = Q.front();
        Q.pop();

        for (int i = 0; i < G[node].size(); i++) {
            int nextNode = G[node][i];

            if (C[node][nextNode] == F[node][nextNode]) continue;
            if (checked[nextNode]) continue;

            T[nextNode] = node;
            checked[nextNode] = true;

            if (nextNode == destination) continue;
            Q.push(nextNode);
        }
    }

    return checked[destination];
}

int main() {
    int N;
    in >> N;

    for (int i = 1; i <= N; i++) {
        int x, y;
        in >> x >> y;

        G[source].push_back(i);
        G[i].push_back(source);

        G[i + offset].push_back(destination);
        G[destination].push_back(i + offset);

        C[source][i] = x;
        C[i + offset][destination] = y;

        for (int j = 1; j <= N; j++) {
            if (i == j) continue;

            G[i].push_back(j + offset);
            G[j + offset].push_back(i);
            C[i][j + offset] = 1;
        }
    }

    int maxFlow = 0;
    while (BFS())
        for (int i = 0; i < G[destination].size(); i++) {
            int node = destination, flow = inf;
            std::vector<int> solution;

            T[destination] = G[destination][i];
            while (node != source) {
                flow = std::min(flow, C[T[node]][node] - F[T[node]][node]);
                node = T[node];
            }

            if (flow <= 0) continue;

            node = destination;
            while (node != source) {
                F[T[node]][node] += flow;
                F[node][T[node]] -= flow;

                node = T[node];
                solution.push_back(node);
            }
            maxFlow += flow;
    }

    out << maxFlow << "\n";
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            if (F[i][j + offset] == 1) out << i << " " << j << "\n";
}