Cod sursa(job #2586375)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 20 martie 2020 18:36:09
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <bits/stdc++.h>
using namespace std;

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

class FlowNetwork {
  private:
    int n, s, t;
    vector<vector<int>> ad, cap;

    bool bfs(vector<bool>& vis, vector<int>& father) {
        fill(vis.begin(), vis.end(), false);
        vis[s] = true;
        queue<int> q; q.push(s);
        while (!q.empty()) {
            int node = q.front(); q.pop();
            for (int nghb : ad[node])
                if (!vis[nghb] && cap[node][nghb]) {
                    vis[nghb] = true;
                    father[nghb] = node;
                    if (nghb != t)
                        q.push(nghb);
                }
        }
        return vis[t];
    }

  public:
    FlowNetwork(int n, int s, int t) :
        n(n), s(s), t(t), ad(n + 1),
        cap(n + 1, vector<int>(n + 1)) { }

    void addEdge(int x, int y, int z = 1) {
        ad[x].push_back(y);
        ad[y].push_back(x);
        cap[x][y] = z;
    }

    auto maxFlow() {
        vector<bool> vis(n + 1);
        vector<int> father(n + 1);
        int maxFlow = 0;
        while (bfs(vis, father))
            for (int nghb : ad[t])
                if (vis[nghb] && cap[nghb][t]) {
                    int flow = 1e9;
                    father[t] = nghb;
                    for (int i = t; i != s; i = father[i])
                        flow = min(flow, cap[father[i]][i]);
                    for (int i = t; i != s; i = father[i]) {
                        cap[father[i]][i] -= flow;
                        cap[i][father[i]] += flow;
                    }
                    maxFlow += flow;
                }

        pair<int, vector<pair<int, int>>> ans;
        ans.first = maxFlow;
        int x = (n - 1) / 2;
        for (int i = 1; i <= x; i++)
            for (int j = 1; j <= x; j++)
                if (cap[j + x][i])
                    ans.second.emplace_back(i, j);
        return ans;
    }
};

int main() {
    int n; fin >> n;
    FlowNetwork graph(2 * n + 1, 0, 2 * n + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (j != i)
                graph.addEdge(i, j + n);

    for (int i = 1; i <= n; i++) {
        int out, in; fin >> out >> in;
        graph.addEdge(0, i, out);
        graph.addEdge(i + n, 2 * n + 1, in);
    }

    auto ans = graph.maxFlow();
    fout << ans.first << '\n';
    for (auto edge : ans.second)
        fout << edge.first << ' ' << edge.second << '\n';

    fout.close();
    return 0;
}