Cod sursa(job #1223311)

Utilizator Paula-ElenaPaula-Elena Margarit Paula-Elena Data 26 august 2014 21:08:44
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <cstring>
#include <fstream>
#include <queue>
using namespace std;

const int MAXN = 103;

int N, S, D, cf[2*MAXN][2*MAXN], tata[2*MAXN];

void read()
{
    ifstream fin("harta.in");

    fin >> N;
    S = 0;
    D = 2*N + 1;
    for (int i = 1; i <= N; ++i)
        fin >> cf[S][i] >> cf[i+N][D];

    fin.close();
}

inline void relax(int x, int y, int c)
{
    cf[x][y] -= c;
    cf[y][x] += c;
}

bool BFS(int S, int D)
{
    memset(tata, -1, sizeof tata);
    queue < int > Q;

    Q.push(S);
    while ( !Q.empty() )
    {
        int x = Q.front();
        Q.pop();

        for (int i = 1; i <= D; ++i)
            if ( cf[x][i] && tata[i] == -1 )
            {
                Q.push(i);
                tata[i] = x;
            }
    }

    return tata[D] != -1;
}

int fluxMax()
{
    int flux = 0;

    while ( BFS(S, D) )
        for (int i = N + 1; i <= 2*N; ++i)
            if ( cf[i][D] && tata[i] != -1 )
            {
                int f = cf[i][D];
                for (int j = i ; j != S; j = tata[j] )
                    f = min(f, cf[ tata[j] ][j]);

                relax(i, D, f);

                for (int j = i; j != S; j = tata[j] )
                    relax(tata[j], j, f);

                flux += f;
            }

    return flux;
}

int main()
{
    read();

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            cf[i][j+N] = (i != j);

    ofstream fout("harta.out");
    fout << fluxMax() << '\n';
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if ( i != j && !cf[i][j+N] )
                fout << i << ' ' << j << '\n';

    fout.close();

    return 0;
}