[shkola] Re: 'Dyzdovnata' zadacha

> Ei vi i moia dazd..
Neka da wali togawa. I ot men dxzhd! Hwashta wsichki testowe.

I edin malxk comentar. 10 klas, kazwajte kakwo wi e qsno i kakwo ne wi e 
qsno. Chetete li wxoshte postowete w shkolata? Zashtoto naposledxk 
zabelqzah che nie s Ludo mnogo sme kachili tempoto. Za nas ne e 
problem. Ako ima takxw za was pishete. Ako imate idei po zadachi 
sxshto! Wxobshte, towa ne e mailing list samo za nas s Ludo.

-- 
Ivaylo Riskov <ivaylo_riskov@xxxxxxx>

"If it happens, it must be possible."

#include <stdio.h>
#include <stdlib.h>

#define MAX_NODE        1000
#define MAX_EDGE        2000

typedef struct {
        int node;
        double water;
} SEdge;

typedef struct {
        int h;
        int n;
        double water;
} SNode;

SEdge edges[MAX_NODE][MAX_EDGE];
int edge_count[MAX_NODE];

SNode nodes[MAX_NODE];
SNode *sorted[MAX_NODE];

int v, e;

int fcmp(const void *e1, const void *e2) {
        SNode *s1, *s2;

        s1 = *(SNode **)e1;
        s2 = *(SNode **)e2;
        return s2->h - s1->h;
}

void read() {
        int i, x, y;
        double w;
        
        scanf("%i %i", &v, &e);
        for (i = 0; i < v; i++) {
                scanf("%i", &nodes[i].h);
                nodes[i].water = 0;
                nodes[i].n = i;
                sorted[i] = nodes + i;
        }

        for (i = 0; i < e; i++) {
                scanf("%i %i %lf", &x, &y, &w);
                x--; y--;
                if (nodes[x].h == nodes[y].h) {
                        nodes[x].water += w/2;
                        nodes[y].water += w/2;
                        continue;
                }

                if (nodes[x].h < nodes[y].h)
                        x ^= y, y ^= x, x ^= y;

                edges[x][edge_count[x]].node = y;
                edges[x][edge_count[x]].water = w;
                edge_count[x]++;
        }
}

void flow_down(SNode *node) {
        int i;
        double f;

        if (!edge_count[node->n])
                return;
        
        f = node->water/edge_count[node->n];
        node->water = 0.0;
        
        for (i = 0; i < edge_count[node->n]; i++)
                nodes[edges[node->n][i].node].water += edges[node->n][i].water 
+ f;
}

int main() {
        int i;
        
        read();
        qsort(sorted, v, sizeof(SNode *), fcmp);
        
        for (i = 0; i < v; i++)
                flow_down(sorted[i]);
        
        for (i = 0; i < v; i++) 
                if (nodes[i].water > 0.0)
                        printf("%i %.4lf\n", i + 1, nodes[i].water);
        return 0;
}

Other related posts: