Cod sursa(job #2962257)

Utilizator witekIani Ispas witek Data 8 ianuarie 2023 02:59:34
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

int n, m, s, t;
vector <vector<int>> v, cap;
vector <int> parrent;
vector <bool> visited;

void init() {
    t = 2 * n + 1;
    cap = vector <vector<int>> (t + 1, vector <int> (t + 1));
    v = vector <vector <int>> (t + 1);
    parrent = vector <int> (t + 1);
    visited = vector <bool> (t + 1);
}

void read() {
    fin >> n;
    init();
    int x, y;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(i != j) {
                v[i].push_back(j + n);
                v[j + n].push_back(i);
                cap[i][j + n] = 1;
            }
    for(int i = 1; i <= n; i ++) {
        fin >> x >> y;
        v[s].push_back(i);
        v[i].push_back(s);
        cap[s][i] = x;
        v[i + n].push_back(t);
        v[t].push_back(i + n);
        cap[i + n][t] = y;
    }
    /*
    for(int i = 1; i <= t; i ++, cout << '\n') {
        cout << i << " : ";
        for (const auto &node: v[i])
            cout << node << " ";
    }
    cout << '\n';
    for(int i = 1; i <= t; i ++, cout << '\n')
        for(int j = 1; j <= t; j ++)
            cout << cap[i][j] << " ";
            */
}

bool bfs() {
    fill(visited.begin(), visited.end(), 0);
    queue <int> q;
    q.push(s);
    visited[s] = true;
    int node;
    while(!q.empty()) {
        node = q.front();
        q.pop();
        if(node == t)
            continue;
        for(const auto& i : v[node]) {
            if(!visited[i] && cap[node][i]) {
                parrent[i] = node;
                visited[i] = true;
                q.push(i);
            }
        }
    }
    return visited[t];
}

int getMaxFlow() {
    int ansFlow = 0;
    while(bfs()) {
        for(const auto& i : v[t]) {
            if(!visited[i])
                continue;
            int minFlow = 2e9;
            parrent[t] = i;
            for (int node = t; node != s; node = parrent[node]) {
                if (cap[parrent[node]][node] < minFlow)
                    minFlow = cap[parrent[node]][node];
            }
            if(minFlow == 0)
                continue;
            ansFlow += minFlow;
            for (int node = t; node != s; node = parrent[node]) {
                cap[parrent[node]][node] -= minFlow;
                cap[node][parrent[node]] += minFlow;
            }
        }
    }
    return ansFlow;
}

void solve() {
    fout << getMaxFlow() << '\n';

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j++)
            if(i != j && !cap[i][n + j])
                fout << i << " " << j << '\n';


}

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