Cod sursa(job #2966929)

Utilizator mariailincailinca maria nechita mariailinca Data 18 ianuarie 2023 18:15:40
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <bits/stdc++.h>

using namespace std;

// Complexitate O(N * M^2)

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

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

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]) {
                tata[i] = node;
                visited[i] = true;
                q.push(i);
            }
        }
    }
    return visited[t];
}

int getMaxFlow() {
    int F = 0;
    while(bfs()) {
        for(const auto& i : v[t]) {

            if(!visited[i])
                continue;
            int minFlow = 2e9;
            tata[t] = i;
            for (int node = t; node != s; node = tata[node]) {
                // gaseste capacitatea minima a muchiilor
                if (cap[tata[node]][node] < minFlow)
                    minFlow = cap[tata[node]][node];
            }
            if(minFlow == 0)
                continue;
            F += minFlow;

            //parcurgere drum pt a actualiza capacitatile muchiilor
            for (int node = t; node != s; node = tata[node]) {
                cap[tata[node]][node] -= minFlow;
                cap[node][tata[node]] += minFlow;
            }
        }
    }
    return F;
}

int main() {

    fin >> n;
    t = 2 * n + 1;
    cap = vector <vector<int>> (t + 1, vector <int> (t + 1));
    v = vector <vector <int>> (t + 1);
    tata = vector <int> (t + 1);
    visited = vector <bool> (t + 1);


    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            if(i != j) {
                v[i].push_back(j + n);  // adauga o muchie de la nodul i la nodul j+n cu cap 1
                v[j + n].push_back(i);
                cap[i][j + n] = 1;
            }

    int x, y;
    for(int i = 1; i <= n; i ++) {
        fin >> x >> y;
        v[s].push_back(i); // adauga muchie de la nodul sursa la nodul i cu capacitate x
        v[i].push_back(s);
        cap[s][i] = x;

        v[i + n].push_back(t); //adauga muchie de la nodul cu capacitaete y la nodul destinatie
        v[t].push_back(i + n);
        cap[i + n][t] = y;
    }
    fout << getMaxFlow() << '\n';

    //daca nu exista nici o capacitate pe marginea dintre nodul curent si nodul adiacent
    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';
    return 0;
}