INFOMAN брой 18

/*
 Задача 3. Пороен Дъжд
 Условие:
 Даден е граф с N < 1000 върха (кръстовища) и M < 2000 ребра (улици). Всеки
 връх има определена височина, а всяко ребро - дължина. Улиците са заляти от
 дъжд по такъв начин, че всяка улица събира количество вода равно на дължина-
 та и. Водата от улиците се оттича по следния начин: ако единия и край е по-
 ниско, всичката вода се оттича натам, ако и двата края са еднакво високи,
 водата се разделя по равно. Ако от едно кръстовище тръгват улици към по-
 долни кръстовища, водата от него се разделя по равно между тях. В противен
 случай тя се натрупва там. Намерете на кои кръстовища се събира вода и
 водата събрана във всяко от тях.

 Решение:
 Ще симулираме изтичането на водата постъпково. Т.е. на всяка стъпка ако на
 едно кръстовище с отточни улици (такива, на които въпросното кръстовище е
 горен край) има вода, ние я разпределяме между другите краища на тези улици.
 За да докажем, че алгоритъма е коректен, ще е достатъчо да докажем, че той
 винаги свършва и, че не се "губи" никаква вода при конкретното му изпълнение.
 За първата част е достатъчно да видим, че ако от даден връх с вода тръгват
 пътища надолу, тя се оттича, а ако не тръгват, тя стои там (което се иска и
 от условието.) Съществено е, че няма начин вода от по-ниско кръстовище да
 попадне на по-високо, т.е. рано или късно всичката вода ще попадне на кръст-
 овища без отточни улици (своеобразни локални минимуми) и алгоритъма ще
 свърши.
 Втората част на доказателството е нужна заради факта, че е възможно след като
 оттечем един връх (евентуално и наследниците му,) на него отново да се
 натрупа вода. Но съгласно законите на елементарната аритметика, резултатът
 от това разминаване, ще е също верен, т.к. няма значение дали оттичаме водата
 от един връх наведнъж или на няколко пъти.
 Заради спецификата на входа и нашето желание сорсовите файлове да нямат нужда
 от входен и изходен файл, съм преддефинирал входните данни, но който се
 интересува от начина по който съм изпълнил входа, може да види закоментарения
 сорс.
*/

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

#define MAX_N 1000
#define MAX_M 2000

unsigned int height[] = { 0, 130, 110, 150, 110, 180 };  /*височина на кръстовищата*/
unsigned int neigh_n[] = { 0, 1, 0, 2, 0, 3 };/*брой на съседите на всяко кръстовище*/
unsigned neigh[][MAX_N] = {{ 0, 0, 0, 0 },         /*списък на съседите*/
                           { 0, 2, 0, 0 },
                           { 0, 0, 0, 0 },
                           { 0, 1, 2, 0 },
                           { 0, 0, 0, 0 },
                           { 0, 2, 3, 4 }};
double water[] = { 0, 50, 195, 40, 35, 0 };  /*първоначална вода във всяко кръстовище*/

int n = 5 , m = 7;

int main( void )
{
  int i, j, k, l, moretodo;
/*
  scanf( "%d %d", &n, &m );
  for( i = 1; i <= n; i++ ) scanf( "%d", &height[i] );
  for( i = 0; i < m; i++ )
  {
    scanf( "%d %d %d", &j, &k, &l );
    if( height[j] > height[k] )
      water[k] += l,
      neigh[j][++neigh_n[j]] = k;
    else if( height[j] < height[k] )
    {
      water[j] += l,
      neigh[k][++neigh_n[k]] = j;
    }
    else
      water[j] += (double)l / 2,
      water[k] += (double)l / 2;
  }
*/
  for(; moretodo;)
  {
    moretodo = 0;
    for( i = 1; i <= n; i++ )
      if( neigh_n[i] && water[i] )
      {
	moretodo = 1;
	for( j = 1; j <= neigh_n[i]; j++ )
	  water[neigh[i][j]] += water[i] / neigh_n[i];
	water[i] = 0;
      }
  }

  l = 0;
  for( i = 1; i <= n; i++ )
    if( !neigh_n[i] )
    {
      if( l ) printf( "\n" );
      l = 1;
      printf( "%d %.4lf", i, water[i] );
    }

  return 0;
}