Cod sursa(job #2080734)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 3 decembrie 2017 14:42:34
Problema Taramul Nicaieri Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

const int inf = 2000000000;

struct Muchie {
    int to, rev, flow, cap;
};

vector <Muchie> g[204];
int n, src, dr;

queue <int> q;
int dist[204];
int bfs() {
    memset(dist, 0, sizeof(dist));
    q.push(src);
    dist[src] = 2;

    while(!q.empty()) {
        int from = q.front();
        for(int k = 0; k < g[from].size(); ++ k) {
            Muchie &e = g[from][k];

            if(dist[e.to] == 0 && e.flow < e.cap) {
                dist[e.to] = dist[from] + 1;
                q.push(e.to);
            }
        }
        q.pop();
    }

    return (dist[dr] > 0);
}

int minim(int a, int b) {
    if(a > b)
        return b;
    return a;
}

int rem[204];
int dfs(int from, int minflow) {
    if(from == dr) {
        return minflow;
    } else {
        while(rem[from] < g[from].size()) {
            Muchie e = g[from][rem[from]];

            if(dist[from] == dist[e.to] - 1) {
                int deltaflow = dfs(e.to, minim(minflow, e.cap - e.flow));

                if(deltaflow > 0) {
                    g[from][rem[from]].flow += deltaflow;
                    g[e.to][e.rev].flow -= deltaflow;
                    return deltaflow;
                }
            }

            ++ rem[from];
        }
        return 0;
    }
}

int maxflow() {
    int raspuns = 0, deltaflow;
    while(bfs() == 1) {
        memset(rem, 0, sizeof(rem));
        do {
            deltaflow = dfs(src, inf);
            raspuns += deltaflow;
        }while(deltaflow > 0);
    }
    return raspuns;
}

int main() {
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);

    scanf("%d", &n);
    n *= 2;
    src = n ++;
    dr = n ++;

    for(int i = 0; i < n - 2; i += 2) {
        int out, in;
        scanf("%d%d", &out, &in);

        g[i].push_back({dr, g[dr].size(), 0, in});
        g[dr].push_back({i, g[i].size() - 1, 0, 0});

        g[src].push_back({i + 1, g[i + 1].size(), 0, out});
        g[i + 1].push_back({src, g[src].size() - 1, 0, 0});

        for(int j = 0; j < n - 2; j += 2) {
            if(j != i) {
                g[i + 1].push_back({j, g[j].size(), 0, 1});
                g[j].push_back({i + 1, g[i + 1].size() - 1, 0, 0});
            }
        }
    }

    printf("%d\n", maxflow());

    for(int i = 1; i < n - 2; i += 2) {
        for(int j = 0; j < g[i].size(); ++ j) {
            if(g[i][j].flow > 0) {
                printf("%d %d\n", i / 2 + 1, g[i][j].to / 2 + 1);
            }
        }
    }

    return 0;
}