Cod sursa(job #2415084)

Utilizator eduardcadarCadar Eduard eduardcadar Data 25 aprilie 2019 15:15:15
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
#include <climits>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
#define nmax 205
int n, x, y, m, A[nmax][nmax], fl, t[nmax], sursa, dest;
bool u[nmax];
vector<int> v[nmax];
void afis() {
    for (int i = 1; i <= n; ++i) {
        for (int j = n + 1; j < dest; ++j) if (A[j][i]) g << i << ' ' << j - n << '\n';
    }
}
int bfs() {
    memset(t,-1,sizeof(t));
    memset(u,0,sizeof(u));
    int Q[nmax], p(0), q(0);
    Q[0] = sursa;
    u[sursa] = 1;
    while (p <= q) {
        int nod = Q[p++];
        for (int i = 0; i < v[nod].size(); ++i) {
            int x = v[nod][i];
            if (!u[x] && A[nod][x] > 0) {
                t[x] = nod;
                Q[++q] = x;
                u[x] = 1;
            }
        }
    }
    if (t[dest] + 1) return 1;
    return 0;
}
void muchii() {
    for (int i = 1; i <= n; ++i) v[sursa].push_back(i), v[i].push_back(sursa);
    for (int i = 1; i <= n; ++i)
        for (int j = n + 1; j < dest; ++j) if (i+n != j) v[i].push_back(j), v[j].push_back(i), A[i][j] = 1;
    for (int i = n + 1; i < dest; ++i) v[i].push_back(dest), v[dest].push_back(i);
}
int main()
{
    f >> n;
    sursa = 0, dest = 2 * n + 1;
    muchii();
    for (int i = 1; i <= n; ++i) {
        f >> x >> y;
        m += x;
        A[sursa][i] = x;
        A[n + i][dest] = y;
    }
    g << m << '\n';
    fl = 0;
    while (bfs()) {
        for (int i = 1; i <= dest; ++i) {
            if (t[i] + 1 && A[i][dest] > 0) {
                int mini = INT_MAX;
                mini = min(mini, A[i][dest]);
                for (int j = i; j != sursa; j=t[j]) mini = min(mini,(A[t[j]][j]));
                if (mini < 0) continue;
                A[i][dest] -= mini;
                for (int j = i; j != sursa; j=t[j]) A[t[j]][j] -= mini, A[j][t[j]] += mini;
                fl += mini;
            }
        }
    }
    afis();
    return 0;
}