Cod sursa(job #2663289)

Utilizator radugnnGone Radu Mihnea radugnn Data 25 octombrie 2020 21:58:12
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda trainingflow Marime 2.44 kb
#include <fstream>
#include <iostream>
#include <bitset>
#include <vector>
#include <deque>
#define DIM 210
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
bitset<DIM> U;
vector<int> L[DIM];
int C[DIM][DIM], F[DIM][DIM], T[DIM];
deque<int> q;
pair <int, int> sol[100010];
int n, m, i, x, y, z, flux, cp, p, mn, j, d, cnt;
int bfs() {
    int destinatie = 0;
    U.reset();
    U[0] = 1;
    q.push_back(0);
    while (!q.empty()) {
        int nod = q.front();
        for (int i = 0; i < L[nod].size(); i++) {
            int vecin = L[nod][i];
            if (U[vecin] == 0 && C[nod][vecin] > F[nod][vecin]) {
                U[vecin] = 1;
                q.push_back(vecin);
                T[vecin] = nod;
                if (vecin == 2 * n + 1)
                    destinatie = 1;

            }

        }
        q.pop_front();
    }
    return destinatie;

}
int main() {
    fin >> n;
    for (i = 1; i <= n; i++) {
        fin >> x >> y;
        C[0][i] = x;
        C[n + i][2 * n + 1] = y;
        L[0].push_back(i);
        L[i].push_back(0);
        L[n + i].push_back(2 * n + 1);
        L[2 * n + 1].push_back(n + i);
    }
    for (i = 1; i <= n; i++)
        for (j = n + 1; j <= 2 * n; j++) {
            if (j - i != n) {
                L[i].push_back(j);
                L[j].push_back(i);
                C[i][j] = 1;
            }
        }
    d = 2 * n + 1;
    while (bfs()) {
        for (i = 0; i < L[d].size(); i++) {
            p = L[d][i];
            if (C[p][d] > F[p][d] && U[p] == 1) {
                mn = C[p][d] - F[p][d];
                cp = p;
                while (cp) {
                    if (C[T[cp]][cp] - F[T[cp]][cp] < mn)
                        mn = C[T[cp]][cp] - F[T[cp]][cp];
                    cp = T[cp];
                }
                F[p][d] += mn;
                F[d][p] -= mn;
                cp = p;
                while (cp) {
                    F[T[cp]][cp] += mn;
                    F[cp][T[cp]] -= mn;
                    cp = T[cp];
                }
            }
        }
    }
    for (i = 1; i <= n; i++)
        for (j = n + 1; j <= 2 * n; j++)
            if (F[i][j]) {
                sol[++cnt].first = i;
                sol[cnt].second = j - n;
            }
    fout << cnt << "\n";
    for (i = 1; i <= cnt; i++)
        fout << sol[i].first << " " << sol[i].second << "\n";

    return 0;
}