Cod sursa(job #2957629)

Utilizator mirceaspPetcu Mircea mirceasp Data 23 decembrie 2022 01:33:08
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
#define mx 10001
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
#define minim min(x,flux)
int n, iesire,intrare;
int rgraf[2 * mx][2 * mx];

bool bfs(int s, int t,int tata[], bool vizitat[]) {
    queue<int> q;
    vizitat[s] = true;
    tata[s] = -1;
    q.push(s);
    while (!q.empty()) {
        int front = q.front();
        q.pop();
        for (int i = 1; i <= t; ++i) {
            if (vizitat[i] == false && rgraf[front][i] > 0) {
                if (i == t) {
                    tata[i] = front;
                    return true;
                }
                vizitat[i] = true;
                q.push(i);
                tata[i] = front;
            }
        }
    }
    //daca se poate ajunge la destinatie
    return vizitat[t];
}

int main() {
    f >> n;

    for(int i = 1;i<=n;i++)
    {
        f>>iesire>>intrare;
        rgraf[0][i] = iesire;
        rgraf[i+n][2*n+1] = intrare;
    }
    for(int i = 1;i<=n;i++)
        for (int j = n+1; j <= 2*n; ++j) {
            if(j-n != i)
                rgraf[i][j] = 1;
        }

    int tata[2*n + 2];
    for (int i = 0; i < 2*n + 2; i++)
        tata[i] = -1;

    bool vizitat[2*n + 2];
    for (int i = 0; i <2*n + 2; i++)
        vizitat[i] = false;

    vector<int> veciniFinal;
    for (int i = n + 1; i <= 2*n; i++)
        veciniFinal.push_back(i);

    int cuplaje = 0;

    while (bfs(0, 2*n +1, tata, vizitat)) {
        for (auto j: veciniFinal) {
            if (rgraf[j][2*n + 1] > 0 && vizitat[j] == true) {
                tata[2*n + 1] = j;

                int flux = INT_MAX;
                int u = 2*n + 1;
                while (u != 0) {
                    int x = rgraf[tata[u]][u];
                    flux = minim;
                    u = tata[u];
                }

                if (flux != 0) {
                    cuplaje += 1;
                    u = 2*n + 1;
                    while (u != 0) {
                        int vecin = tata[u];
                        rgraf[vecin][u] -= flux;
                        rgraf[u][vecin] += flux;
                        u = tata[u];
                    }
                }

            }
        }
        for (int i = 0; i <= 2*n + 1; i++)
            tata[i] = -1;
        for (int i = 0; i <= 2*n + 1; i++)
            vizitat[i] = false;

    }

    g << cuplaje << '\n';

    for (int i = 1; i <= n; ++i) {
        for (int j = n + 1; j <= 2*n; ++j) {
            if (rgraf[i][j] == 0 && rgraf[j][i] != 0)
                g << i << ' ' << j - n << '\n';
        }
    }
    f.close();
    f.close();
    return 0;
}