Cod sursa(job #2975533)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 6 februarie 2023 18:34:47
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
class Flow {
    const ll flow_max = 1e18;
    struct Edge {
        int from, to;
        ll c;
        Edge(int a, int b, ll _c) : from(a), to(b), c(_c) {}
    };

public:
    vector <Edge> edges;
    int n, s, t, k;
    vector <int> lvl, rem;
    vector <vector <int>> g;

    bool bfs() {
        fill(lvl.begin(), lvl.end(), 0);
        queue <int> q; q.push(s); lvl[s] = 1;
        while(!q.empty()) {
            int top = q.front(); q.pop();
            for(int id : g[top])
                if(!lvl[edges[id].to] && edges[id].c) {
                    lvl[edges[id].to] = lvl[top] + 1;
                    q.push(edges[id].to);
                }
        }
        return lvl[t];
    }
    Flow(int _n, int _s, int _t) : n(_n), s(_s), t(_t), k(0), lvl(_n + 1, 0), rem(_n + 1, 0), g(_n + 1) {}

    void add_edge(int u, int v, int w, int rw = 0) {
        edges.emplace_back(u, v, w);
        edges.emplace_back(v, u, rw);
        g[u].push_back(k++);
        g[v].push_back(k++);
    }

    ll dfs(int u, ll flow) {
        if(flow == 0) return 0;
        if(u == t) return flow;
        for(int& cid = rem[u]; cid < (int)g[u].size(); cid++) {
            int id = g[u][cid];
            int v = edges[id].to;
            if(!edges[id].c || lvl[v] != lvl[u] + 1) continue;
            ll f = dfs(v, min(flow, edges[id].c));
            if(f == 0) continue;
            edges[id].c -= f;
            edges[id ^ 1].c += f;
            return f;
        }
        return 0;
    }

    ll dinic() {
        ll f = 0;
        while(bfs()) {
            fill(rem.begin(), rem.end(), 0);
            while(ll flow = dfs(s, flow_max))
                f += flow;
        }
        return f;
    }
};
const int N = 100 + 5;
int indeg[N], outdeg[N];
const int INF = 1e9;

int main()
{
    ifstream cin("harta.in");
    ofstream cout("harta.out");
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> indeg[i] >> outdeg[i];
    }
    /// 1...n -> IN nodes
    /// n+1...2n -> OUT nodes
    /// 2n+1 source
    /// 2n+2 sink
    int s = 2 * n + 1, t = 2 * n + 2;
    Flow F(2 * n + 2, s, t);
    for(int i = 1; i <= n; i++)
        F.add_edge(s, i, indeg[i]);
    for(int i = 1; i <= n; i++)
        F.add_edge(n + i, t, outdeg[i]);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) if(i != j) {
            F.add_edge(i, n + j, 1);
        }
    }
    cout << F.dinic() << "\n";
    for(auto [u, v, w] : F.edges) {
        if(u <= 2 * n && v <= n && w) {
            cout << u - n << " " << v << "\n";
        }
    }
    return 0;
}