Cod sursa(job #2308195)

Utilizator lupulescu2001Lupulescu Vlad lupulescu2001 Data 26 decembrie 2018 16:08:50
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

const int nMax = 100, oo = 2000000000;
vector<int> g[2 * nMax + 5];
int n, c[2 * nMax + 5][2 * nMax + 5], viz[2 * nMax + 5], t[2 * nMax + 5], in[nMax + 5], out[nMax + 5], f, flow;
queue<int> q;

int BF() {
    memset(viz, 0, sizeof(viz));
    viz[0] = 1;
    q.push(0);
    while (q.size()) {
        int dad = q.front();
        q.pop();
        if (dad == f)
            continue;
        for (auto i : g[dad]) {
            if (viz[i] == 0 && c[dad][i] > 0) {
                q.push(i);
                viz[i] = 1;
                t[i] = dad;
            }
        }
    }
    return viz[f];
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> in[i] >> out[i];
    }
    f = 2 * n + 1;
    for (int i = 1; i <= n; i++) {
        g[0].push_back(i);
        g[i].push_back(0);
        g[f].push_back(i + n);
        g[i + n].push_back(f);
        c[0][i] = in[i];
        c[i + n][f] = out[i];
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i == j)
                continue;
            g[i].push_back(j + n);
            g[j + n].push_back(i);
            c[i][j + n] = 1;
        }
    while (BF()) {
        int fmin = oo;
        for (int i = f; i; i = t[i])
            fmin = min(fmin, c[t[i]][i]);
        for (int i = f; i; i = t[i]) {
            c[t[i]][i] -= fmin;
            c[i][t[i]] += fmin;
        }
        flow += fmin;
    }
    fout << flow << '\n';
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j && c[i][n + j] == 0)
                fout << i << " " << j << '\n';
    return 0;
}