Cod sursa(job #1223381)

Utilizator mihai995mihai995 mihai995 Data 28 august 2014 02:42:54
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#include <cstring>
using namespace std;

const int N = 100, NR = 2 * N + 1;

class Queue{
    int v[NR], st, dr;

public:
    void reset(){
        st = dr = 0;
    }

    inline void push(int x){
        v[st++] = x;
    }

    inline int pop(){
        return v[dr++];
    }

    inline bool isEmpty(){
        return st == dr;
    }
};

int cf[NR][NR], T[NR], n;
Queue Q;

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

bool bfs(int x, int D){
    memset(T, -1, sizeof(T));
    Q.reset();
    Q.push(x);

    while (!Q.isEmpty()){
        x = Q.pop();
        for (int y = 1 ; y <= D ; y++)
            if ( T[y] == -1 && cf[x][y] ){
                Q.push(y);
                T[y] = x;
            }
    }

    return T[D] != -1;
}

int maxFlow(int S, int D){
    int flow = 0;

    while ( bfs(S, D) )
        for (int x = n + 1 ; x <= 2 * n ; x++){
            int F = cf[x][D];

            if (!F) continue;

            for (int i = x ; i != S ; i = T[i])
                F = min(F, cf[ T[i] ][i]);

            if (!F) continue;

            for (int i = x ; i != S ; i = T[i])
                relax(T[i], i, F);
            flow += F;
        }
    return flow;
}

int main(){
    ifstream in("harta.in");

    in >> n;
    int S = 0, D = 2 * n;

    for (int i = 1 ; i <= n ; i++)
        in >> cf[S][i] >> cf[i + n][D];

    in.close();

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

    ofstream out("harta.out");

    out << maxFlow(S, D) << '\n';
    for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j <= n ; j++)
            if ( i != j && !cf[i][j + n] )
                out << i << ' ' << j << '\n';

    out.close();

    return 0;
}