Cod sursa(job #1874507)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 10 februarie 2017 02:02:29
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("harta.in");
ofstream fo("harta.out");

const int NMAX = 256;

int n, s, src, snk;

vector<int> g[NMAX];
int cap[NMAX][NMAX],
    flx[NMAX][NMAX],
    gws[NMAX],
    far[NMAX],
     in[NMAX],
     ut[NMAX];

inline int in_nod(const int &nod) { return 2 * nod; }
inline int ut_nod(const int &nod) { return 2 * nod + 1; }

void make_net() {
    src = 0;
    snk = 1;

    for (int i = 1; i <= n; ++i) {
        g[src].push_back(ut_nod(i)), g[ut_nod(i)].push_back(src), cap[src][ut_nod(i)] = ut[i];
        g[snk].push_back(in_nod(i)), g[in_nod(i)].push_back(snk), cap[in_nod(i)][snk] = in[i];
        for (int j = 1; j <= n; ++j) if (i != j) {
            g[ut_nod(i)].push_back(in_nod(j));
            g[in_nod(j)].push_back(ut_nod(i));
            cap[ut_nod(i)][in_nod(j)] = 1; } } }

void pump() {
    deque<int> q;
    int u, aug;

    while (true) {
        static int it = 0; ++it;

        q.push_back(src);
        gws[src] = it;

        while (!q.empty()) {
            u = q.front();
            q.pop_front();

            for (auto v: g[u]) if (gws[v] != it && cap[u][v] - flx[u][v] > 0) {
                q.push_back(v);
                gws[v] = it;
                far[v] = u; } }

        if (gws[snk] < it)
            break;

        for (auto lnk: g[snk]) {
            aug = cap[lnk][snk] - flx[lnk][snk];

            for (int nod = lnk; nod != src; nod = far[nod])
                aug = min(aug, cap[far[nod]][nod] - flx[far[nod]][nod]);

            for (int nod = lnk; nod != src; nod = far[nod]) {
                flx[far[nod]][nod]+= aug;
                flx[nod][far[nod]]-= aug; }

            flx[lnk][snk]+= aug;
            flx[snk][lnk]-= aug; } } }

int main(void) {
    int s = 0;

    fi >> n;

    for (int i = 1; i <= n; ++i) {
        fi >> ut[i] >> in[i];
        s+= in[i]; }

    make_net();
    pump();

    fo << s << '\n';
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        if (flx[ut_nod(i)][in_nod(j)])
            fo << i << ' ' << j << '\n';

    return 0; }