Cod sursa(job #2962246)

Utilizator witekIani Ispas witek Data 8 ianuarie 2023 02:23:59
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 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;
vector <int> parrent;
vector <bool> visited;

void init() {
    t = 2 * n + 1;
    v = vector <vector<int>> (t + 1, 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 ++) {
        fin >> x >> y;
        v[s][i] = x;
        v[n + i][t] = y;

        for(int j = 1; j <= n; j++)
            if(i != j)
                v[i][n + j] = 1;
    }


}

bool bfs() {
    fill(visited.begin(), visited.end(), 0);
    fill(parrent.begin(), parrent.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(int i = 1; i <= t; i ++) {
            if(!visited[i] && v[node][i]) {
                parrent[i] = node;
                visited[i] = true;
                q.push(i);
            }
        }
    }
    return visited[t];
}

int getMaxFlow() {
    int ansFlow = 0;
    while(bfs()) {
        for(int i = 1; i <= n; i ++) {
            if(!visited[n + i])
                continue;
            int minFlow = 2e9;
            parrent[t] = n + i;
            for (int node = t; node != s; node = parrent[node]) {
                if (v[parrent[node]][node] < minFlow)
                    minFlow = v[parrent[node]][node];
            }
            if(minFlow == 0)
                continue;
            ansFlow += minFlow;
            for (int node = t; node != s; node = parrent[node]) {
                v[parrent[node]][node] -= minFlow;
                v[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(!v[i][n + j]&& i != j)
                fout << i << " " << j << '\n';

}

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