Cod sursa(job #3189240)

Utilizator Ricardo03Petrovici Ricardo Ricardo03 Data 4 ianuarie 2024 18:13:23
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.06 kb
#include <bits/stdc++.h>
using namespace std;
 
const int inf = 1e9;
int ans[250][250];
 
struct Dinic {
    struct edge {
        int to, rev;
        int flow, w;
        int id;
    };
 
    int n, s, t, mxid;
    vector <int> d, flow_through;
    vector <int> done;
    vector <vector <edge>> g;
 
 
    Dinic() {}
 
 
    Dinic(int _n) {
        n = _n + 10;
        mxid = 0;
        g.resize(n);
    }
 
 
    void add_edge(int u, int v, int w, int id = -1) {
        edge a = {v, g[v].size(), 0, w, id};
        edge b = {u, g[u].size(), 0, 0, -2};
        g[u].emplace_back(a);
        g[v].emplace_back(b);
        mxid = max(mxid, id);
    }
 
    
    bool bfs() {
        d.assign(n, -1);
        d[s] = 0;
        queue <int> q;
        q.push(s);
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(auto &e : g[u]) {
                int v = e.to;
                if(d[v] == -1 && e.flow < e.w) 
                    d[v] = d[u] + 1, q.push(v);
            }
        }
        return d[t] != -1;
    }
 
    int dfs(int u, int flow) {
        if (u == t) {
            return flow;
        }
        for(int &i = done[u]; i < g[u].size();i++) {
            edge &e = g[u][i];
            if(e.w <= e.flow) 
                continue;
            int v = e.to;
            if(d[v] == d[u] + 1) {
                int nw = dfs(v, min(flow, e.w - e.flow));
                if(nw > 0) {
                    e.flow += nw;
                    g[v][e.rev].flow -= nw;
                    ans[u][v] += nw;
                    ans[v][u] -= nw;
                    return nw;
                }
            }
        }
        return 0;
    }
 
    int max_flow(int _s, int _t) {
        s = _s;
        t = _t;
        int flow = 0;
        while (bfs()) {
            done.assign(n, 0);
            while(int nw = dfs(s, inf)) {
                flow += nw;
            }
        }
 
        flow_through.assign(mxid + 10, 0);
        for(int i = 0; i < n; i++) 
            for(auto e : g[i]) 
                if(e.id >= 0) 
                    flow_through[e.id] = e.flow;
        return flow;
    }
};
 
int main()
{
    ifstream f("harta.in");
    ofstream g("harta.out");
    int n, m;
    f >> n;
    int a[n + 5], b[n + 5], sumb = 0;
    
    for(int i = 1; i <= n; i++) {
        f >> a[i] >> b[i];
        sumb += b[i];
    }
 
    Dinic G(2 * n);
    
    int src = 2 * n + 1, trg = 2 * n + 2;
    for(int i = 1; i <= n; i++) {
        G.add_edge(src, i, a[i]);
        G.add_edge(i + n, trg, b[i]);
    }
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i != j) {
                G.add_edge(i, j + n, 1);
            }
        }
    }
 
    int sol = G.max_flow(src, trg);

    g << sumb << "\n";
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(ans[i][j + n] == 1) {
                g << i << " " << j << "\n";
            }
        }
    }
 
    return 0;
}