Cod sursa(job #3188878)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 3 ianuarie 2024 22:48:54
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.21 kb
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
const int INF = 1e9;

struct Edge {
    int x;
    int flow;
    int cap;
    int nxt;
};

struct Dinic {
    int source;
    int sink;
    int n;
    vector <vector <Edge>> gr;
    vector <int> dist;
    vector <int> start;
    Dinic(int _source, int _sink, int _size) {
        source = _source;
        sink = _sink;
        n = _size;
        gr.resize(_size);
        dist.resize(_size);
        start.resize(_size);
    }
    void add_edge(int x, int y, int cap) {
        gr[x].push_back({y, 0, cap, (int)gr[y].size()});
        gr[y].push_back({x, 0, 0, (int)gr[x].size() - 1});
    }
    bool bfs() {
        for (int i = 0; i < n; i++)
            dist[i] = -1;
        dist[source] = 0;
        queue <int> q;
        q.push(source);
        while (q.size()) {
            int node = q.front();
            q.pop();
            for (auto vec : gr[node]) {
                if (dist[vec.x] == - 1 && vec.cap > vec.flow) {
                    dist[vec.x] = dist[node] + 1;
                    q.push(vec.x);
                }
            }
        }
        return dist[sink] != -1;
    }
    int dfs(int node, int sink, int flow) {
        if (node == sink)
            return flow;
        while (start[node] < gr[node].size()) {
            Edge e = gr[node][start[node]];
            if (dist[e.x] == dist[node] + 1 && e.flow < e.cap) {
                int new_flow = dfs(e.x, sink, min(flow, e.cap - e.flow));
                if (new_flow > 0) {
                    gr[node][start[node]].flow += new_flow;
                    gr[e.x][e.nxt].flow -= new_flow;
                    return new_flow;
                }
            }
            start[node]++;
        }
        return 0;
    }
    int maxflow() {
        int ans = 0;
        while (bfs()) {
            int flow;
            for (auto &x : start) x = 0;
            while (flow = dfs(source, sink, INF))
                ans += flow;
        }
        return ans;
    }
    vector <pair <int, int>> get_edges() {
        vector <pair <int, int>> ans;
        int sz = (n - 2) / 2;
        for (int i = 0; i < sz; i++) {
            for (auto vec : gr[i]) {
                if (vec.flow == 1) {
                    ans.push_back({i, vec.x});
                }
            }
        }
        return ans;
    }
};

int main () {
    freopen ("harta.in", "r", stdin);
    freopen ("harta.out", "w", stdout);
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n;
    cin >> n;
    int source = 2 * n, sink = 2 * n + 1;
    Dinic network (source, sink, 2 * n + 2);
    for (int i = 0; i < n; i++) {
        for (int j = n; j < 2 * n; j++) {
            if (i != j - n)
                network.add_edge (i, j, 1);
        }
    }
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        network.add_edge (source, i, x);
        network.add_edge (i + n, sink, y);
    }
    cerr << network.maxflow() << "\n";
    auto ans = network.get_edges();
    cout << ans.size() << "\n";
    for (auto it : ans)
        cout << it.first + 1 << " " << it.second - n + 1 << "\n";
    return 0;
}