Kod był wyświetlany 1254 razy.
/*
Name: Inwestycja
Copyright: GPL GNU
Author: Przemysław Pastuszka
Date: 27-11-2007 19:20:58
Description:
Sieć komputerowa Bajtelandii składa się z węzłów połączonych światłowodami.
Sieć światłowodów nie jest zbyt gęsta. Umożliwia nawiązanie połączenia
(być może pośredniego) pomiędzy dowolnymi dwoma węzłami w sieci tylko w jeden sposób. To powoduje,
że na niektórych łączach powstaje spory tłok i następują duże opóźnienia w przesyłaniu informacji.
Natomiast ruch w sieci jest dość spory i w zasadzie jednakowo natężony, tzn. w każdej jednostce czasu,
każde dwa węzły wymieniają pomiędzy sobą pakiet informacji. Obciążeniem łącza nazwiemy liczbę pakietów
przesyłanych przez to łącze w jednej jednostce czasu.
(Zauważmy, że obciążenie łącza, to liczba węzłów znajdujących się po jednej
stronie łącza pomnożona przez liczbę węzłów położonych po drugiej stronie
łącza.) Firma zarządzająca siecią zastanawia się, czy obciążenie sieci jest
na tyle duże, by konieczna była modernizacja lub rozbudowa sieci. W tym
celu chciałaby się dowiedzieć, jakie jest największe obciążenie łącza w sieci.
Zadanie
Napisz program, który obliczy, ile wynosi obciążenie najbardziej obciążonego
łącza w sieci.
Wejście
Program powinien czytać dane z wejścia standardowego. W pierwszym wierszu
podana jest liczba ( ), która oznacza liczbę węzłów w sieci. W kolejnych
wierszach opisane są łącza sieci, po jednym w wierszu. Opis łącza składa się z
dwóch liczb oddzielonych spacją; liczby te oznaczają numery węzłów, pomiędzy
którymi przebiega łącze.
Wyjście
Program powinien pisać wynik na wyjście standardowe. Wynikiem powinna być jedna
liczba oznaczająca obciążenie najbardziej obciążonego łącza w sieci.
Przykład
Dla danych wejściowych:
5
1 2
2 3
3 4
3 5
poprawną odpowiedzią jest:
6
*/
#include <iostream>
#include <conio.h>
using namespace std;
struct Krawedz
{
int nr,wartosc;
Krawedz* next;
};
struct Lista
{
Krawedz *glowa, *ogon;
};
Lista *ls;
bool *czy;
void Dodaj(int a, int b)
{
Krawedz *wsk=new Krawedz;
wsk->next=NULL;
wsk->nr=b;
wsk->wartosc=0;
if(ls[a].glowa==NULL)
ls[a].glowa=ls[a].ogon=wsk;
else
ls[a].ogon=ls[a].ogon->next=wsk;
}
int Przejdz(int nr)
{
czy[nr]=true;
Krawedz *wsk=ls[nr].glowa;
int suma=0;
while(wsk!=NULL)
{
if(czy[wsk->nr]==false)
{
wsk->wartosc=Przejdz(wsk->nr)+1;
suma+=wsk->wartosc;
}
wsk=wsk->next;
}
return suma;
}
int maxim=0;
void Oblicz(int nr, int rodzic, int ile)
{
czy[nr]=true;
Krawedz *wsk=ls[nr].glowa;
int suma=0;
while(wsk!=NULL)
{
if(wsk->nr==rodzic)
wsk->wartosc=ile;
suma+=wsk->wartosc;
wsk=wsk->next;
}
wsk=ls[nr].glowa;
while(wsk!=NULL)
{
if((wsk->wartosc*(suma-wsk->wartosc+1))>maxim)
maxim=wsk->wartosc*(suma-wsk->wartosc+1);
if(czy[wsk->nr]==false)
Oblicz(wsk->nr,nr,suma-wsk->wartosc+1);
wsk=wsk->next;
}
}
int main()
{
int n;
cout<<"\n\n\tPodaj n : ";
cin>>n;
ls=new Lista[n+1];
czy=new bool[n+1];
for(int i=1;i<n+1;i++)
{
ls[i].glowa=ls[i].ogon=NULL;
czy[i]=false;
}
int a,b;
for(int i=0;i<n-1;i++)
{
cin>>a>>b;
Dodaj(a,b);
Dodaj(b,a);
}
Przejdz(1);
for(int i=1;i<n+1;i++)
czy[i]=false;
Oblicz(1,0,0);
cout<<maxim;
getch();
return 0;
}
Pobierz plik tekstowy