Cod sursa(job #2951505)

Utilizator alex_bb8Banilean Alexandru-Ioan alex_bb8 Data 6 decembrie 2022 17:30:34
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 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);
    vector<bool> visited(NMAX, false);
    queue<int> Q;
    
    Q.push(s);
    visited[s] = true;
    parent[s] = -1;
    
    while(!Q.empty()){
        int node = Q.front();
        Q.pop();
        
        for(auto i : G[node]){
            if(!visited[i] && RG[node][i]){
                
                if(i == t){
                    parent[i] = node;
                    return true;
                }
                
                Q.push(i);
                parent[i] = node;
                visited[i] = true;
            }
        }
    }
    
    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] = in[i];
        G[s].push_back(i);
        G[i].push_back(s);
        
        RG[n + i][t] = out[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] = RG[j][i] = 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;
}