Cod sursa(job #3262754)

Utilizator CReaper1116Shang Cheng Lin CReaper1116 Data 11 decembrie 2024 15:52:44
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.25 kb
#include<bits/stdc++.h>
#define cin fin
#define cout fout
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int inf = 1e9;
const int N = 1e2;
struct MFDinitz{
    struct Edge{
        int u, w, cap, flow;
        Edge(int _u, int _w, int _cap){
            u = _u;
            w = _w;
            cap = _cap;
            flow = 0;
        }
    };
    vector<Edge> e;
    vector<vector<int>>e2;
    int n, source, sink;
    MFDinitz(int _n, int _source, int _sink){
        n = _n;
        source = _source;
        sink = _sink;
        e2.resize(n);
    }
    void add_edge(int u, int w, int cap){
        e2[u].push_back(e.size());
        e.push_back(Edge(u, w, cap));
        e2[w].push_back(e.size());
        e.push_back(Edge(w, u, 0));
    }
    vector <int> dist;
    vector <int> pt;
    vector <int> path;
    void graph_algorithm(){
        dist = vector<int>(n, -1);
        dist[source] = 0;
        queue <int> q;
        q.push(source);
        while(!q.empty()){
            int node = q.front();
            q.pop();
            for(auto edgeid : e2[node]){
                Edge edge = e[edgeid];
                if(edge.flow == edge.cap)continue;
                if(dist[edge.w] == -1){
                    dist[edge.w] = dist[edge.u] + 1;
                    q.push(edge.w);
                }
            }
        }
    }
    int dfs(int node){
        if(node == sink){
            return inf;
        }
        while(pt[node] < e2[node].size()){
            int id = e2[node][pt[node]];
            Edge edge = e[id];
            if(edge.flow < edge.cap && dist[edge.w] == dist[edge.u] + 1){
                int x = dfs(edge.w);
                if(x > 0){
                    path.push_back(id);
                    return min(x, edge.cap - edge.flow);
                }
            }
            pt[node]++;
        }
        return 0;
    }
    int max_flow(){
        int f = 0;
        while(1){
            graph_algorithm();
            if(dist[sink] == -1)break;
            pt = vector<int>(n, 0);
            while(1){
                path.clear();
                int nr = dfs(source);
                if(nr == 0)break;
                for(auto i : path){
                    e[i].flow+=nr;
                    e[i^1].flow-=nr;
                }
                f+=nr;
            }
        }
        return f;
    }
};
int main(){
    int n, a = 0, b = 0;
    cin>>n;
    MFDinitz flow(2*n + 2, 0, 2*n + 1);
    for(int i = 0;i < n;i++){
        int u, w;
        cin>>u>>w;
        a+=u;
        b+=w;
        flow.add_edge(0, i + 1, u);
        flow.add_edge(i + 1 + n, 2*n + 1, w);
    }
    for(int i = 1;i <= n;i++){
        for(int j = n + 1;j <= 2*n;j++){
            if(i != j - n){
                flow.add_edge(i, j, 1);
            }
        }
    }
    if(a == b && flow.max_flow() == a){
        cout<<a<<'\n';
        for(int i = 1;i <= n;i++){
            for(auto j : flow.e2[i]){
                auto edge = flow.e[j];
                if(n + 1 <= edge.w && edge.w <= 2*n && edge.cap == edge.flow){
                    cout<<edge.u<<' '<<edge.w - n<<'\n';
                }
            }
        }
    }
    return 0;
}