[shkola] Be quick... or be dead.

Eti ti network flow s BFS i s DFS. Kakto i dva scripta na Perl koito
empirichno dokazaha che BFS Rulez ;-). To se ochakvashe vzemajki na predvid
kakvo sa kazali umnite hora v knigite ama iskash kod, eto ti kod.

btw realizaciqta mi vzaimstva edna idejka ot knigata na Dobrikov i Nakov. Ne
se muchat horata s obratni rebra, pravi rebra, s tova da smqtat ima li mqsto
za oshte potok -- prosti si promenqt kapacitetite na rebrata v dvizhenie --
mnogo qko. ('use the source Luke' ili 'read the f***ing manual' za poveche
informaciq).

A za tezi, koito nqmat nervi da chakat (ili prosto nqmat UNIX mashina s Perl
na neq) eto kakvo kazva scripta (pulen random.

Statistics for 100 cases
BFS total time: 6.61999999999993
DFS total time: 1161.75
DFS was better on 6 cases

Ne znam tochno na koi testove DFS e bilo po-byrzo ot BFS (i s kolko tochno)
obache kato se vidi total time stava qsno koj shte e dead sled testovete na
zhurito.

I sega ako nqkoj mi kazhe che programistite ne sme ludi. Tva go chakah 20 min
da mi kazhe neshto koeto i taka si go znaeh. Po zabavnoto e che se muchih 1
chas s dokumentaciqta na Perl che da si napisha scriptovete za merene na
vremeto. Obshto vzeto edno vreme kato mi kazvaha kakvo shte stana ne vqrvah
obche e verno che edin programist(/hacker) e gotov da izgubi cql den v pisane
na kod/chetene na dokumentaciq samo i samo da si spesti 5 min dosadna
ednoobrazna rabota.

P.S. Bring your daugther... ... to the slaughter...
Pak sym na Iron Maiden ne mi obryshtajte vnimanie.

-- 
Rangel Dokov



#include <stdio.h>
#include <limits.h>
#include <string.h>

#define MAXN            1024
#define INFINITY        INT_MAX

#define MIN(a, b)       ( (a)<(b)?(a):(b) )

// comment this out to use DFS to find the increasing path
#define USE_BFS

// the number of nodes in the graph
int nodes;
// the number of edges in the graph
int edges;
// adjecency matrix holding capacities of each node
// node 0 is the `super source', last node is the 'super destination'
int adj[MAXN][MAXN];
// the current flwo for each edge
int flow[MAXN][MAXN];

void read();
void solve();
void print();
int increase_flow_bfs();
int increase_flow_dfs();

//
// input format
// 1st line - 4 integers the number of nodes N, the number of edges E, the
// number of source nodes S and number of destination nodes D.
// 1 <= N <= 1000, 1 <= S, D <= N
// E lines describing the edges - start node, end node, capacity
// S lines with the numbers of source nodes
// D lines with the numbers of destination nodes
//
void read() {
        int i;
        int tmp1, tmp2;
        int source_cnt, dest_cnt;

        scanf("%d%d%d%d", &nodes, &edges, &source_cnt, &dest_cnt);
        nodes++; // we need one more node at the end for the super destination
        // read edges
        for (i = 0; i < edges; i++) {
                scanf("%d%d", &tmp1, &tmp2);
                scanf("%d", &adj[tmp1][tmp2]);
        }
        // read sources list
        for (i = 0; i < source_cnt; i++) {
                scanf("%d", &tmp1);
                adj[0][tmp1] = INFINITY;
        }
        // read destination list
        for (i = 0; i < dest_cnt; i++) {
                scanf("%d", &tmp1);
                adj[tmp1][nodes] = INFINITY;
        }
}

int increase_flow_bfs() {
        int i;
        int parent[MAXN]; // from where we came to each node
        int queue[MAXN]; // bfs needs a queue
        int begin, end; // pointers for the queue
        int curr; // the number of the current node
        int increase; // the maximal flow for the current path

        // initialization
        for (i = 0; i <= nodes; i++)
                parent[i] = -1;
        begin = 0;
        queue[begin] = 0;
        end = 1;

        // find an increasing flow
        while (begin < end) {
                curr = queue[begin++];
                if (curr == nodes)
                        break;

                for (i = 1; i <= nodes; i++) {
                        if ((parent[i] == -1) && (adj[curr][i] > 0)) {
                                queue[end++] = i;
                                parent[i] = curr;
                        }
                }
        }

        // did we find a path
        if (parent[nodes] == -1)
                return 0;

        // find the amount of the flow
        curr = nodes;
        increase = INFINITY;
        while (parent[curr] != -1) {
                increase = MIN(increase, adj[parent[curr]][curr]);
                curr = parent[curr];
        }

        // add the flow
        curr = nodes;
        while (parent[curr] != -1) {
                // modify current flow
                flow[parent[curr]][curr] += increase;
                flow[curr][parent[curr]] -= increase;
                // modify capacities
                adj[parent[curr]][curr] -= increase;
                adj[curr][parent[curr]] += increase;
                curr = parent[curr];
        }
        return increase;
}

// the maximum flow that was found
int tflow;
// mark each node that we have visited
int visited[MAXN];
int dfs(int curr, int cflow) {
        int i;

        if (curr == nodes)
                return cflow;

        visited[curr] = 1;

        for (i = 1; i <= nodes; i++) {
                if (!visited[i] && (adj[curr][i] > 0))
                        if ((tflow = dfs(i, MIN(cflow, adj[curr][i]))) > 0) {
                                // increase flow
                                flow[curr][i] += tflow;
                                flow[i][curr] -= tflow;
                                // modify capacities
                                adj[curr][i] -= tflow;
                                adj[i][curr] += tflow;
                                // ... and get out of here
                                return tflow;
                        }
        }
        return 0;
}

int increase_flow_dfs() {
        memset(visited, 0, MAXN*sizeof(int));
        return dfs(0, INFINITY);
}


void solve() {
        int cont = 1;

        while (cont > 0) {
#ifdef USE_BFS
                cont = increase_flow_bfs();
#else
                cont = increase_flow_dfs();
#endif
        }
}

void print() {
        int i;
        int total = 0;

        for (i = 0; i < nodes; i++)
                total += flow[i][nodes];

        printf("%d\n", total);
}

int main() {
        read();
        solve();
        print();
        return 0;
}


#!/usr/bin/perl

my $MAXN = 200;
my $MAX_CAP = 1000;

my $nodes = int (rand()*$MAXN);
my $edges = int (rand()*$nodes*$nodes/2);
my $source_cnt = int (rand()*$nodes/10) | 1;
my $dest_cnt = int (rand()*$nodes/10) | 1;
my $tmp1, $tmp2, $tmp3;

print "$nodes $edges $source_cnt $dest_cnt\n";

for (0..$edges) {
        $tmp1 = int (rand()*$nodes);
        $tmp2 = int (rand()*$nodes);
        $tmp3 = int (rand()*$MAX_CAP);
        print "$tmp1 $tmp2 $tmp3\n";
}

for (0..$source_cnt) {
        $tmp1 = int (rand()*$nodes);
        print "$tmp1\n";
}

for (0..$dest_cnt) {
        $tmp1 = int (rand()*$nodes);
        print "$tmp1\n";
}


#!/usr/bin/perl

my $test_cases = 100;
my $total_bfs = 0;
my $curr_bfs;
my $total_dfs = 0;
my $curr_dfs;
my $tmp;
my $won = 0;

my @tmp1, @tmp2;

for (1..$test_cases) {
        print "Test case #$_\n";
        open ifile, ">input" or die $!;

        print ifile `./gentest.pl`;

        @tmp1 = times;
        my $res1 = `./flow_bfs < input`;
        @tmp2 = times;
        $curr_bfs = $tmp2[2] - $tmp1[2];

        @tmp1 = times;
        my $res2 = `./flow_dfs < input`;
        @tmp2 = times;
        $curr_dfs = $tmp2[2] - $tmp1[2];

        if ($curr_bfs > $curr_dfs) {
                $won++;
        }
        if ($res1 != $res2) {
                print "SOMETHING BAD HAPPENED\nANSWERS DON'T MATCH\n";
        }
        $total_bfs += $curr_bfs;
        $total_dfs += $curr_dfs;
}

print "Statistics for $test_cases cases\n";
print "BFS total time: $total_bfs\n";
print "DFS total time: $total_dfs\n";
print "DFS was better on $won cases\n";

Other related posts: