[shkola] Re: 'Dyzdovnata' zadacha

Ei vi i moia dazd.. backa za vsicki testoveSamo na edin po nerazbiraemi
pricini se razlicava s 0.0001. Prastam ia inline ce mi e trudno da ia
attch :) .. :
#include <stdio.h>
#define MAX_NUM 2000
int n,m;
int height[MAX_NUM];
int path[MAX_NUM][MAX_NUM];
int visited[MAX_NUM];
int numvs[MAX_NUM];
double capac[MAX_NUM];
int n,m;
double round(double num) {
       int round_val =num*10000;

       if ((round_val)%10 >5)
          return num+0.0001;
       else
          return num;          
}
void read() {
     int i,src,dest,dist;
    
    scanf("%d %d\n" , &n, &m);
    for (i=1;i<=n;i++)
        scanf("%d\n",&height[i]);
        
        for (i=1;i<=m;i++) {
        scanf("%d %d %d", &src, &dest, &dist);
        if (height[src] != height[dest]) {
                if (height[src] > height[dest]) {
                                path[src][dest] = 1;
                numvs[src]++;
                                        capac[dest] += dist;
                                                }
                                                    else {
                                                                path[dest][src] 
= 1;
                numvs[dest]++;
                                        capac[src] += dist;
                                                }
                                                 }
         else {
                capac[src] += (double)dist/2;
                capac[dest] += (double)dist/2;
         }
        
    }
}

int getheighest() {
    int max = -1;
    int i;
    
    for (i= 1; i<=n;i++)
        if (!visited[i])
        if ((max == -1) || (height[i]>height[max])) {
           max = i;
               }
        
    return max;
}

void flowit(int emptynode) {
     int i;
    double new_val  = (double) capac[emptynode] / numvs[emptynode];
    
    capac[emptynode] = 0;
    
    for (i=1; i<=n;i++)
        if (path[emptynode][i] != 0 )
           capac[i]+=new_val;
}

void doflow() {
     int i;
    
    for ( i = 1; i<=n;i++)  {
        int next = getheighest();
        
                visited[next] = 1;
        
        if (numvs[next] != 0)
                flowit(next);
    }
}

void write() {
     int i;
    
    for (i=1; i<=n; i++)
        if (capac[i] != 0 ) {
            round(capac[i]);
            printf("%d %.4f\n", i, capac[i]);
        }
}

int main() {
    read();
    doflow();
    write();
    return 0;
}

Other related posts: