Cod sursa(job #2691044)

Utilizator AlexVulpoiuAlexandru Vulpoiu AlexVulpoiu Data 26 decembrie 2020 20:05:53
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <fstream>

using namespace std;

int n, m, i, j, k, min1;
int bfs[205], tata[205], c[205][205], flux[205][205];
bool viz[205];

bool BFS() {
    int p;

    for(i = 0; i <= n; i++)
        viz[i] = false;
    p = 1;
    bfs[0] = 0;
    viz[0] = true;
    for(i = 0; i < p; i++) {
        k = bfs[i];
        if(k != n)
            for(j = 1; j <= n; j++)
                if(j != k && !viz[j] && flux[k][j] < c[k][j]) {   /// daca vecinul curent nu este vizitat si muchia nu este folosita la
                    viz[j] = true;                                /// capacitate maxima
                    bfs[p++] = j;
                    tata[j] = k;
                }
    }

    return viz[n];
}

int main() {
    ifstream f("harta.in");
    ofstream g("harta.out");

    f >> n;
    for(i = 1; i <= n; i++)
        f >> c[0][i] >> c[n + i][n * 2 + 1];
    f.close();

    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            if(i != j)
                c[i][n + j] = 1;
    n = n * 2 + 1;

    m = 0;
    while(BFS())
        for(i = n / 2 + 1; i < n; i++) {
            k = i;
            if(viz[k] && flux[k][n] < c[k][n]) {    /// daca nodul a fost vizitat si pot mari fluxul
                tata[n] = k;                        /// actualizez tatal lui n din bfs
                min1 = 2000000000;
                for(j = n; j; j = tata[j])
                    min1 = min(min1, c[tata[j]][j] - flux[tata[j]][j]);
                if(min1 != 0) {
                    for(j = n; j; j = tata[j]) {
                        flux[tata[j]][j] += min1;
                        flux[j][tata[j]] -= min1;
                    }
                    m++;
                }
            }
        }

    g << m << '\n';
    for(i = 1; i <= n / 2; i++)
        for(j = n / 2 + 1; j <= n; j++)
            if(flux[i][j] == 1)
                g << i << ' ' << j - n / 2 << '\n';
    g.close();

    return 0;
}