Inwestycje
Kod był wyświetlany 1218 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
Załączniki
Administrator WJL
PHP&SQL coded by NOVA-IT