Cod sursa(job #3181354)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 6 decembrie 2023 21:30:21
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct Edge{
    int u, v;
    T f, c;
    Edge(int u_, int v_, T c_) : u(u_), v(v_), c(c_) {}
};

template<typename T>
struct Dinic{
    vector<Edge<T>> edges;
    vector<vector<pair<int, int>>> adj;
    vector<int> dist, ptr;
    Dinic(int n) : adj(n), dist(n), ptr(n) {}
    void addEdge(int u, int v, T c){ // one direction
        edges.emplace_back(u, v, c);
        adj[u].emplace_back(v, edges.size() - 1);
        edges.emplace_back(v, u, 0);
        adj[v].emplace_back(u, edges.size() - 1);
    }

    bool bfs(int src, int dst){
        fill(dist.begin(), dist.end(), -1);
        dist[src] = 0;
        queue<int> q;
        q.push(src);
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(auto [v, id] : adj[u]){
                if(dist[v] == -1 && edges[id].f < edges[id].c){
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
        return dist[dst] != -1;
    }

    T dfs(int u, int dst, T flow){
        if(u == dst || flow == 0) return flow;
        for(int &i = ptr[u]; i < (int)adj[u].size(); i++){
            auto [v, id] = adj[u][i];
            if(dist[v] == dist[u] + 1 && edges[id].f < edges[id].c){
                T newFlow = dfs(v, dst, min(flow, edges[id].c - edges[id].f));
                if(newFlow > 0){
                    edges[id].f += newFlow;
                    edges[id ^ 1].f -= newFlow;
                    return newFlow;
                }
            }
        }
        return 0;
    }

    T maxFlow(int src, int dst){
        T flow = 0;
        while(bfs(src, dst)){
            fill(ptr.begin(), ptr.end(), 0);
            while(T newFlow = dfs(src, dst, numeric_limits<T>::max())){
                flow += newFlow;
            }
        }
        return flow;
    }
};

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);
    int n;
    cin >> n;
    Dinic<long long> dinic(n * 2 + 2);
    int src = 0, dst = n * 2 + 1;
    for(int i = 1; i <= n; i++){
        int x, y;
        cin >> x >> y;
        dinic.addEdge(src, i, x);
        dinic.addEdge(i + n, dst, y);
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i != j)
                dinic.addEdge(i, j + n, 1);
    dinic.maxFlow(src, dst);
    vector<pair<int, int>> ans;
    for(int i = 1; i <= n; i++){
        for(auto [v, id] : dinic.adj[i]){
            if(dinic.edges[id].f == 1 && v != src)
                ans.emplace_back(i, v - n);
        }
    }
    cout << ans.size() << "\n";
    for(auto [u, v] : ans)
        cout << u << " " << v << "\n";
    return 0;
}