Cod sursa(job #3189599)

Utilizator DragosC1Dragos DragosC1 Data 6 ianuarie 2024 11:30:03
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <fstream>
#include <iostream>
#include <set>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <stack>
#include <ctime>
#include <fstream>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
 
#define ll long long

const ll INF = 1e18;

struct Dinic {
    int n, s, t;
    vector<int> dist;
    vector<int> done;
    vector<vector<int>> g;
    vector<vector<ll>> cap, flow;

    Dinic(int _n = 0) {
        n = _n + 10;
        g.resize(n + 1);
        cap.resize(n + 1, vector<ll>(n + 1));
        flow.resize(n + 1, vector<ll>(n + 1));
    }

    void init(int _n) {
        n = _n + 10;
        g.resize(n + 1);
        cap.resize(n + 1, vector<ll>(n + 1));
        flow.resize(n + 1, vector<ll>(n + 1));
    }

    void add_edge(int u, int v, ll w) {
        g[u].push_back(v);
        g[v].push_back(u);
        cap[u][v] = w;
    }

    bool bfs() {
        dist.assign(n, -1);
        dist[s] = 0;
        queue <int> q;
        q.push(s);
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto &v : g[u]) {
                if (dist[v] == -1 && cap[u][v] > flow[u][v]) 
                    dist[v] = dist[u] + 1, q.push(v);
            }
        }
        if (dist[t] != -1)
            return 1;
        return 0;
    }

    ll dfs(int u, ll _flow) {
        if (u == t) {
            return _flow;
        }

        for (int &i = done[u]; i < g[u].size(); i++) {
            int v = g[u][i];
            if (cap[u][v] <= flow[u][v]) 
                continue;

            if (dist[v] == dist[u] + 1) {
                ll nw = dfs(v, min(_flow, cap[u][v] - flow[u][v]));
                if (nw > 0) {
                    flow[u][v] += nw;
                    flow[v][u] -= nw;
                    return nw;
                }
            }
        }
        return 0;
    }

    ll max_flow(int _s, int _t) {
        s = _s;
        t = _t;
        ll _flow = 0;
        while (bfs()) {
            done.assign(n, 0);
            while(ll nw = dfs(s, INF)) {
                _flow += nw;
            }
        }
        return _flow;
    }
};


int main() {
    int n, s, t;
    ifstream f("harta.in");
    f >> n;
    Dinic d(2 * n + 10);
    s = 2 * n + 1;
    t = s + 1;
    for (int i = 0; i < n; i++) {
        int out, in;
        f >> out >> in;
        d.add_edge(s, i, out);
        d.add_edge(i + n, t, in);
    }
    f.close();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (i == j)
                continue;
            d.add_edge(i, j + n, 1);
        }
    ofstream g("harta.out");
    g << d.max_flow(s, t) << '\n';
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (i == j)
                continue;
            if (d.flow[i][j + n] == 1)
                g << i + 1 << ' ' << j + 1 << '\n';
        }
    g.close();
    return 0;
}