Cod sursa(job #2951548)

Utilizator alex_bb8Banilean Alexandru-Ioan alex_bb8 Data 6 decembrie 2022 18:53:46
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("harta.in");
ofstream g("harta.out");

const int NMAX = 202;

int n, in[NMAX], out[NMAX], RG[NMAX][NMAX];
vector<int> G[NMAX];

void read(){

    f >> n;

    for(int i = 1; i <= n; ++i){
        f >> out[i] >> in[i];
    }

}

bool BFS(int s, int t, vector<int>& parent){
    fill(parent.begin(), parent.end(), -1);
    queue<int> Q;

    Q.push(s);
    parent[s] = -2;

    while(!Q.empty()){
        int node = Q.front();
        Q.pop();

        for(auto i : G[node]){
            if(parent[i] == -1 && RG[node][i]){
                parent[i] = node;

                if(i == t)
                    return true;

                Q.push(i);
            }
        }
    }

    return false;
}

void solve(){

    int max_flow = 0, s = 0, t = 2 * n + 1;
    vector<int> parent(NMAX, -1);

    for(int i = 1; i <= n; ++i){
        RG[s][i] = out[i];
        G[s].push_back(i);
        G[i].push_back(s);

        RG[n + i][t] = in[i];
        G[n + i].push_back(t);
        G[t].push_back(n + i);
    }

    for(int i = 1; i <= n; ++i)
        for(int j = n + 1; j <= 2 * n; ++j)
            if(n + i != j){
                RG[i][j] = 1;
                G[i].push_back(j);
                G[j].push_back(i);
            }
    
    while(BFS(s, t, parent)){
        
        int path_flow = INT_MAX;
        
        // find the max flow through the path
        for(int node = t; node != s; node = parent[node]){
            int aux = parent[node];
            path_flow = min(path_flow, RG[aux][node]);
        }
        
        // update
        for(int node = t; node != s; node = parent[node]){
            int aux = parent[node];
            RG[aux][node] -= path_flow;
            RG[node][aux] += path_flow;
        }
        
        max_flow += path_flow;
    }
    
    g << max_flow << '\n';
    
    for(int i = 1; i <= n; ++i){
        for(int j = n + 1; j <= 2 * n; ++j)
            if(n + i != j && RG[i][j] == 0)
                g << i << ' ' << j - n << '\n'; 
    }
    
}

int main(){
    
    read();
    
    solve();

    return 0;
}