Cod sursa(job #1777104)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 12 octombrie 2016 02:54:04
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("harta.in");
ofstream fout("harta.out");

int source, destination, N, x, y, solution;
int C[256][256], F[256][256], T[256];
vector <int> L[256];
bitset <256> v;
queue  <int> Q;

inline bool BFS()
{
    v.reset();

    Q.push(source);

    while(!Q.empty())
    {
        int node = Q.front();
        Q.pop();

        for(int i = 0; i < L[node].size(); i ++)
        {
            int neighbour = L[node][i];

            if(v[neighbour] == 0 && C[node][neighbour] > F[node][neighbour])
            {
                Q.push(neighbour);
                v[neighbour] = 1;
                T[neighbour] = node;

            }
        }
    }
    if(v[destination] == 1)
    {
        return true;
    }
    return false;
}

int main()
{
    fin >> N;

    source = 0;
    destination = 2 * N + 1;

    for(int i = 1; i <= N; i ++)
    {
        fin >> x >> y;
        L[source].push_back(i);
        L[i].push_back(source);
        C[source][i] = x;
        L[i + N].push_back(destination);
        L[destination].push_back(i + N);
        C[i + N][destination] = y;
    }

    for(int i = 1; i <= N; i ++)
    {
        for(int j = 1; j <= N; j ++)
        {
            if(i ^ j)
            {
                L[i].push_back(j + N);
                L[j + N].push_back(i);
                C[i][j + N] = 1;
            }
        }
    }

    while(BFS())
    {
        int Fmin = (1 << 30);

        for(int i = 0; i < L[destination].size(); i ++)
        {
            int x = L[destination][i];

            if(C[x][destination] > F[x][destination] && v[x] == 1)
            {
                while(x > source)
                {
                    Fmin = min(Fmin, C[ T[x] ][x] - F[ T[x] ][x]);
                    x = T[x];
                }

                x = L[destination][i];
                F[x][destination] += Fmin;
                F[destination][x] -= Fmin;

                while(x > source)
                {
                    F[ T[x] ][x] += Fmin;
                    F[x][ T[x] ] -= Fmin;
                    x = T[x];
                }

                solution += Fmin;

            }
        }
    }

    fout << solution << '\n';

    for(int i = 1; i <= N; i ++)
    {
        for(int j = 1; j <= N; j ++)
        {
            if(F[i][j + N] == 1)
            {
                fout << i << " " << j << '\n';
            }
        }
    }

    return 0;
}