Cod sursa(job #2962308)

Utilizator anamaria_panait.10Panait Ana-Maria anamaria_panait.10 Data 8 ianuarie 2023 10:51:52
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.13 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <stack>
#include <unordered_map>

using namespace std;

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

vector<int> tata;
vector<int> viz;
int a[201][201];
int intr[201], ies[201];
int n, m, src, dest;

int bfs(){
    tata = vector<int>(2 * n + 2);
    viz = vector<int>(2 * n + 2);
    queue <int> q;
    q.push(src);
    viz[src] = 1;
    tata[src] = -1;
    while (!q.empty()){
        int nod = q.front();
        q.pop();
        if(nod == dest)
            return 1;

        for (int i = 1; i <= 2 * n + 1; i++){
            if (!viz[i] && a[nod][i] > 0){
                q.push(i);
                tata[i] = nod;
                viz[i] = 1;
            }
        }
    }
    return 0;
}

int cuplaj(){
    int cup_max = 0, cup = 0;
    while (bfs()){
        for(int i = 1; i <= n; i++){
            if (viz[n + i] && a[n + i][2 * n + 1] > 0){
                cup = 1<<13;
                tata[dest] = n + i;
                for(int nod = dest; nod != src; nod = tata[nod])
                    cup = min(cup, a[tata[nod]][nod]);

                if (cup == 0)
                    continue;

                for (int nod = dest; nod != src; nod = tata[nod]){
                    a[tata[nod]][nod] -= cup;
                    a[nod][tata[nod]] += cup;
                }
                cup_max += cup;
            }
        }
    }
    return cup_max;
}

int main ()
{
    int x, y;
    in >> n;
    for(int i = 1; i <= n; i++){
        in >> x >> y;
        intr[i] = y;
        ies[i] = x;
        a[0][i] = x;
        a[i + n][2 * n + 1] = y;

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

    src = 0;
    dest = 2 * n + 1;
    out << cuplaj() << '\n';

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(a[i][j + n] == 0 && i != j){
                out << i << " " << j << '\n';
            }
        }
    }

    return 0;
}