Cod sursa(job #3190864)

Utilizator david.pasarinDavid Pasarin david.pasarin Data 8 ianuarie 2024 10:37:50
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int NMAX = 205;
int N, c[NMAX][NMAX], f[NMAX][NMAX], pr[NMAX], viz[NMAX], M;
vector<int> v[NMAX], sol[NMAX];

void citire()
{

    fin >> N;
    int x, y;
    for (int i = 1; i <= N; i++)
    {
        fin >> x >> y;
        // nodul 0 este sursa, iar nodul 2*N+1 este destinatia
        // capacitatiile
        c[0][i] += x;
        c[N + i][2 * N + 1] += y;
        // vecinii
        v[0].push_back(i);
        v[i].push_back(0);
        v[N + i].push_back(2 * N + 1);
        v[2 * N + 1].push_back(N + i);
    }
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            if (i != j)
            {
                c[i][N + j] += 1;
                v[i].push_back(N + j);
                v[N + j].push_back(i);
            }
    fin.close();
}

void reset()
{
    for (int i = 0; i <= 2 * N + 1; i++)
        viz[i] = 0;
}

int bfs()
{
    reset();
    viz[0] = 1;
    queue<int> Q;
    Q.push(0);
    while (!Q.empty())
    {
        int prElem = Q.front();
        Q.pop();
        for (int i = 0; i < v[prElem].size(); i++)
        {
            int now = v[prElem][i];
            // daca nu este vizitat si nu este saturat
            if (viz[now] || c[prElem][now] == f[prElem][now])
                continue;
            viz[now] = 1;
            // retin parintele
            pr[now] = prElem;
            Q.push(now);
        }
    }
    // return daca am ajuns la destinatie
    return viz[2 * N + 1];
}

void max_flow()
{
    // cat timp exista drum de la sursa la destinatie
    while (bfs())
    {
        // parcurg drumul de la destinatie la sursa
        for (int i = 0; i < v[2 * N + 1].size(); i++)
        {
            // daca nu este vizitat si nu este saturat
            if (!viz[v[2 * N + 1][i]] || c[v[2 * N + 1][i]][2 * N + 1] == f[v[2 * N + 1][i]][2 * N + 1])
                continue;
            // retin parintele
            pr[2 * N + 1] = v[2 * N + 1][i];
            int minim = 1 << 30;
            // calculez fluxul minim
            for (int act = 2 * N + 1; act != 0; act = pr[act])
                minim = min(minim, c[pr[act]][act] - f[pr[act]][act]);
            // actualizez fluxurile
            for (int act = 2 * N + 1; act != 0; act = pr[act])
            {
                f[pr[act]][act] += minim;
                f[act][pr[act]] -= minim;
            }
        }
    }
    // construiesc solutia
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            if (i != j && f[i][N + j])
                sol[i].push_back(j), ++M;
}

void write()
{

    fout << M << "\n";
    for (int i = 1; i <= N; i++)
        for (int j = 0; j < sol[i].size(); j++)
            fout << i << " " << sol[i][j] << "\n";
    fout.close();
}

int main()
{

    citire();
    max_flow();
    write();
    return 0;
}