Cod sursa(job #2962532)

Utilizator AntoniaPopoviciAntonia-Adelina Popovici AntoniaPopovici Data 8 ianuarie 2023 18:09:28
Problema Taramul Nicaieri Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <bits/stdc++.h>
using namespace std;


// COMPLEXITATE TIMP: O(E*F)
// E = muchii
// F = maxflow

#define NMAX 203
#define INF 0x3f3f3f3f

ifstream fin("harta.in");
ofstream fout("harta.out");
int N, c[NMAX][NMAX], f[NMAX][NMAX], nr_iteratii, d[NMAX], pred[NMAX];
vector <int> coada;

void bf()
{
    int v, i;
    vector <int> ::iterator it;
    d[1] = nr_iteratii;
    coada.push_back(1);
    while (!coada.empty())
    {
        it = coada.end() - 1;
        v = *it;
        coada.pop_back();
        for (i = 1; i <= 2 * N + 2; ++i)
            if (c[v][i] > f[v][i] && d[i] != nr_iteratii)
            {
                d[i] = nr_iteratii;
                pred[i] = v;
                coada.push_back(i);
            }
    }
}

void algoritm(int s, int t)
{
    int min, i;
    ++nr_iteratii;
    while (d[t] != nr_iteratii)
    {
        min = INF;
        bf();
        if (d[t] != nr_iteratii)
            break;
        i = t;
        while (pred[i])
        {
            if (min > c[pred[i]][i] - f[pred[i]][i])
                min = c[pred[i]][i] - f[pred[i]][i];
            i = pred[i];
        }
        i = t;
        while (pred[i])
        {
            f[pred[i]][i] += min;
            f[i][pred[i]] -= min;
            i = pred[i];
        }
        ++nr_iteratii;
    }
}

int main()
{
    int x, y, gt = 0;
    
    fin >> N;
    
    for (int i = 1; i <= N; ++i)
    {
        fin >> x >> y;
        gt += x;
        c[1][i + 1] = x;
        c[N + i + 1][2 * N + 2] = y;
    }
    for (int i = 2; i <= N + 1; ++i)
        for (int j = N + 2; j <= 2 * N + 1; ++j)
            if (i + N != j)
                c[i][j] = 1;
    algoritm(1, 2 * N + 2);
    fout << gt << '\n';

    for (int i = 2; i <= N + 1; ++i)
        for (int j = N + 2; j <= 2 * N + 1; ++j)
            if (f[i][j])
                fout << i - 1 << " " << j - N - 1 << '\n';
    return 0;
}