Cod sursa(job #941133)

Utilizator SteveStefan Eniceicu Steve Data 17 aprilie 2013 23:49:12
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <fstream>
#include <vector>
#include <cstring>
#define pb push_back
using namespace std;

int N, source, sink, M;
vector <int> muchii[211];
int viz[211];
int TT[211];
int cd[211];
int C[211][211];
int F[211][211];

void Citire ()
{
    ifstream fin ("harta.in");
    fin >> N;
    sink = (N << 1) + 1;
    for (int i = 1, a, b; i <= N; i++)
    {
        fin >> a >> b;
        C[source][i] = b;
        C[i + N][sink] = a;
        M += a + b;
    }
    fin.close ();
}

void Make_Graph ()
{
    for (int i = 1; i <= N; i++)
    {
        muchii[i].pb (source);
        muchii[source].pb (i);
        muchii[i + N].pb (sink);
        muchii[sink].pb (i + N);
        for (int j = 1; j < i; j++)
        {
            muchii[j].pb (i + N);
            muchii[i + N].pb (j);
            C[j][i + N] = 1;
        }
        for (int j = i + 1; j <= N; j++)
        {
            muchii[j].pb (i + N);
            muchii[i + N].pb (j);
            C[j][i + N] = 1;
        }
    }
}

int BFS ()
{
    cd[cd[0] = 1] = source;
    memset (viz, 0, sizeof (viz));
    viz[source] = 1;
    for (int i = 1; i <= cd[0]; i++)
    {
        int nod = cd[i];
        for (int j = 0; j < muchii[nod].size (); j++)
        {
            int V = muchii[nod][j];
            if (C[nod][V] == F[nod][V] || viz[V]) continue;
            viz[V] = 1;
            cd[++cd[0]] = V;
            TT[V] = nod;
            if (V == sink) return 1;
        }
    }
    return 0;
}

void Find_Flow ()
{
    while (BFS ())
    {
        int fmin = 2000000000;
        for (int nod = sink; nod != source; nod = TT[nod])
            fmin = min (fmin, C[TT[nod]][nod] - F[TT[nod]][nod]);
        for (int nod = sink; nod != source; nod = TT[nod])
        {
            F[TT[nod]][nod] += fmin;
            F[nod][TT[nod]] -= fmin;
        }
    }
}

void Scriere ()
{
    ofstream fout ("harta.out");
    fout << (M >> 1) << "\n";
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            if (C[i][j + N] && C[i][j + N] == F[i][j + N]) fout << i << " " << j << "\n";
    fout.close ();
}

int main ()
{
    Citire ();
    Make_Graph ();
    Find_Flow ();
    Scriere ();
    return 0;
}