Cod sursa(job #891924)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 25 februarie 2013 21:15:49
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

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

const int MAXN = 210;

int N, S, D;
vector <int> Graf[MAXN];
int C[MAXN][MAXN], F[MAXN][MAXN];
int T[MAXN];
bool Viz[MAXN];

inline bool BFS ()
{
    queue <int> Q;
    vector <int> :: iterator it;
    int nod;

    for (nod = 0; nod <= D; nod ++){
        T[nod] = 0;
        Viz[nod] = 0;
    }

    Q.push (S);
    Viz[S] = 1;
    T[S] = -1;

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

        if (nod == D)
            continue;

        for (it = Graf[nod].begin (); it != Graf[nod].end (); ++ it)
            if (!Viz[*it] && C[nod][*it] != F[nod][*it]){
                Q.push (*it);
                T[*it] = nod;
                Viz[*it] = 1;
            }
    }

    return T[D];
}

void Augment ()
{
    int nod, fmin;
    bool ok = 1;
    vector <int> :: iterator it;

    for ( ; BFS (); )
        for (it = Graf[D].begin (); it != Graf[D].end (); ++ it){
            ok = 1;
            if (!Viz[*it] || C[*it][D] == F[*it][D])
                continue;

            T[D] = *it;

            for (nod = D; nod != S; nod = T[nod])
                if (C[ T[nod] ][nod] == F[ T[nod] ][nod])
                    ok = 0;

            if (!ok)
                continue;

            for (nod = D; nod != S; nod = T[nod]){
                F[ T[nod] ][nod] ++;
                F[nod][ T[nod] ] --;
            }
        }
}

int main()
{
    int M, i, j, a, b;
    int Ans = 0;

    in >> N;
    S = 0;
    D = 2 * N + 1;

    for (i = 1; i <= N; i ++){
        in >> a >> b;
        Ans += a;

        Graf[S].push_back (i);
        Graf[i].push_back (S);
        Graf[D].push_back (i + N);
        Graf[i + N].push_back (D);
        C[S][i] = a;
        C[i + N][D] = b;

        for (j = N + 1; j <= 2 * N; j ++)
            if (i != j - N){
                Graf[i].push_back (j);
                Graf[j].push_back (i);
                C[i][j] = 1;
            }
    }

    Augment ();

    cout << Ans << "\n";
    for (i = 1; i <= N; i ++)
        for (j = N + 1; j <= 2 * N; j ++)
            if (F[i][j] == 1)
                cout << i << " " << j - N << "\n";

    return 0;
}