Cod sursa(job #1437902)

Utilizator sulzandreiandrei sulzandrei Data 18 mai 2015 19:48:51
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 2.19 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int dim = 205;
int N, M, Cc, T[dim], C[dim][dim], F[dim][dim], Q[dim];
vector <int> V[dim];
void addmuc (int a, int b, int c)
{
    if (c <= 0)
        return;
    C[a][b] = c;
    V[a].push_back (b);
    V[b].push_back (a);
}
int bf ()
{
    int p = 0, u = 0, ok = 0, i, n, f;
    Q[0] = 0;
    for (i = 0; i <= M; i++)
        T[i] = -1;
    while (p <= u)
    {
        n = Q[p];
        for (i = 0; i < V[n].size(); i++)
        {
            f = V[n][i];
            if (T[f] == -1 && C[n][f] > F[n][f])
            {
                if (f == M)
                {
                    ok = 1;
                    continue;
                }
                Q[++u] = f;
                T[f] = n;
            }
        }
        p++;
    }
    return ok;
}

void cit ()
{
    in >> N;
    M = N + N + 1;
    for (int i = 1, j, x, y; i <= N; i++)
    {
        in >> x >> y;

        Cc += x;
        addmuc (0, i, x);
        addmuc (N+i, M, y);

        for (j = 1; j <= N; j++)
        {
            if (i != j)
            {
                addmuc (i, N+j, 1);
            }
        }
    }
}
void flux ()
{
    int n, f, m, i;
    while ( bf () )
    {
        for (i = 0; i < V[M].size(); i++)
        {
            if (T[V[N][i]] == 0)
                continue;
            f = M;
            n = V[M][i];
            m = C[n][f] - F[n][f];
            while (f != 0)
            {
                m = min (m, C[n][f] - F[n][f]);
                f = n;
                n = T[f];
            }
            f = M;
            n = V[M][i];
            while (f != 0)
            {
                F[n][f] += m;
                F[f][n] -= m;

                f = n;
                n = T[f];
            }
        }
    }
}

void afi ()
{
    int i, j;
    out << Cc << '\n';
    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
            if (F[i][j+N] == 1)
                out << i << ' ' << j << '\n';
}
int main ()
{
    cit ();
    flux ();
    afi ();
    return 0;
}