[shkola] Zadachi wxrhu algoritmite za grafi

Eto wi nqkolko zadachi, pri koito ima pochti direktno prilozhenie na 
razgledanite algoritmi!

Sxotwetnata zadacha wxrwi s nomera si w acm.uva.es.
Ako nqkoi gi reshi move da gi prashta tam!

Pozdrawi,
        Ivo

==============================================================

        Ivaylo Riskov    <ivaylo_riskov@xxxxxxx>

        "Stenderup's Law:
           The sooner you fall behind, the more time you will have to 
catch up"

==============================================================


 Longest Paths 
 =============

It is a well known fact that some people do not have their social abilities 
completely enabled. One example is the lack of talent for calculating distances 
and intervals of time. This causes some people to always choose the longest way 
to go from one place to another, with the consequence that they are late to 
whatever appointments they have, including weddings and programming contests. 
This can be highly annoying for their friends. 

Cesar has this kind of problem. When he has to go from one point to another he 
realizes that he has to visit many people, and thus always chooses the longest 
path. One of Cesar's friends, Felipe, has understood the nature of the problem. 
Felipe thinks that with the help of a computer he might be able to calculate 
the time that Cesar is going to need to arrive to his destination. That way he 
could spend his time in something more enjoyable than waiting for Cesar. 


Your goal is to help Felipe developing a program that computes the length of 
the longest path that can be constructed in a given graph from a given starting 
point (Cesar's residence). You can assume that there is at least one path from 
this starting point to any destination. Also, the graph has no cycles (there is 
no path from any node to itself), so Cesar will reach his destination in a 
finite time. In the same line of reasoning, nodes are not considered directly 
connected to themselves. 

Input 
=====

The input consists of a number of cases. The first line on each case contains a 
positive number n (1 < n <= 100) that specifies the number of points that Cesar 
might visit (i.e., the number of nodes in the graph).

A value of n = 0 indicates the end of the input. 


After this, a second number s is provided, indicating the starting point in 
Cesar's journey (1 <= s <= n). Then, you are given a list of pairs of places p 
and q, one pair per line, with the places on each line separated by 
white-space. The pair `p q`" indicates that Cesar can visit q after p. 

A pair of zeros (``0 0") indicates the end of the case. 


As mentioned before, you can assume that the graphs provided will not be cyclic 
and that every place will be reachable from the starting place. 

Output 
======
For each test case you have to find the length of the longest path that begins 
at the starting place. You also have to print the number of the final place of 
such longest path. If there are several paths of maximum length, print the 
final place with smallest number.


Print a new line after each test case. 

Sample Input 
============
2
1
1 2
0 0
5
3
1 2
3 5
3 1
2 4
4 5
0 0
5
5
5 1
5 2
5 3
5 4
4 1
4 2
0 0
0


Sample Output 
=============
Case 1: The longest path from 1 has length 1, finishing at 2.

Case 2: The longest path from 3 has length 4, finishing at 5.

Case 3: The longest path from 5 has length 2, finishing at 1.

MPI Maelstrom 
=============

BIT has recently taken delivery of their new supercomputer, a 32 processor 
Apollo Odyssey distributed shared memory machine with a hierarchical 
communication subsystem. Valentine McKee's research advisor, Jack Swigert, has 
asked her to benchmark the new system.

``Since the Apollo is a distributed shared memory machine, memory access and 
communication times are not uniform,'' Valentine told Swigert. ``Communication 
is fast between processors that share the same memory subsystem, but it is 
slower between processors that are not on the same subsystem. Communication 
between the Apollo and machines in our lab is slower yet.''

``How is Apollo's port of the Message Passing Interface (MPI) working out?'' 
Swigert asked.

``Not so well,'' Valentine replied. ``To do a broadcast of a message from one 
processor to all the other n-1 processors, they just do a sequence of n-1 
sends. That really serializes things and kills the performance.''

``Is there anything you can do to fix that?''

``Yes,'' smiled Valentine. ``There is. Once the first processor has sent the 
message to another, those two can then send messages to two other hosts at the 
same time. Then there will be four hosts that can send, and so on.''

``Ah, so you can do the broadcast as a binary tree!''

``Not really a binary tree -- there are some particular features of our network 
that we should exploit. The interface cards we have allow each processor to 
simultaneously send messages to any number of the other processors connected to 
it. However, the messages don't necessarily arrive at the destinations at the 
same time -- there is a communication cost involved. In general, we need to 
take into account the communication costs for each link in our network 
topologies and plan accordingly to minimize the total time required to do a 
broadcast.''

Input
=====

The input will describe the topology of a network connecting n processors. The 
first line of the input will be n, the number of processors, such that 1 <= n 
<= 100.

The rest of the input defines an adjacency matrix, A. The adjacency matrix is 
square and of size n x n. Each of its entries will be either an integer or the 
character x. The value of A(i, j) indicates the expense of sending a message 
directly from node i to node j. A value of x for A(i, j) indicates that a 
message cannot be sent directly from node i to node j.

Note that for a node to send a message to itself does not require network 
communication, so A(i, i) = 0 for 1 <= i <= n. Also, you may assume that the 
network is undirected (messages can go in either direction with equal 
overhead), so that A(i, j) = A(j, i). Thus only the entries on the (strictly) 
lower triangular portion of A will be supplied.

The input to your program will be the lower triangular section of A. That is, 
the second line of input will contain one entry, A(2, 1). The next line will 
contain two entries, A(3, 1)and A(3, 2), and so on.

Output
======

Your program should output the minimum communication time required to broadcast 
a message from the first processor to all the other processors.

Sample Input
============
5
50
30 5
100 20 50
10 x x 10

Sample Output
=============
35
 The Settlers of Catan 
 =====================
Within Settlers of Catan, the 1995 German game of the year, players attempt to 
dominate an island by building roads, settlements and cities across its 
uncharted wilderness. 

You are employed by a software company that just has decided to develop a 
computer version of this game, and you are chosen to implement one of the 
game's special rules: 


When the game ends, the player who built the longest road gains two extra 
victory points. 


The problem here is that the players usually build complex road networks and 
not just one linear path. Therefore, determining the longest road is not 
trivial (although human players usually see it immediately). 


Compared to the original game, we will solve a simplified problem here: You are 
given a set of nodes (cities) and a set of edges (road segments) of length 1 
connecting the nodes. The longest road is defined as the longest path within 
the network that doesn't use an edge twice. Nodes may be visited more than 
once, though. 


Example: The following network contains a road of length 12. 

o        o -- o        o
 \      /      \      /
  o -- o        o -- o
 /      \      /      \
o        o -- o        o -- o
               \      /
                o -- o


Input 
=====
The input file will contain one or more test cases.

The first line of each test case contains two integers: the number of nodes n 
(2 <= n <= 25 ) and the number of edges m (1 <= m <= 25). The next m lines 
describe the m edges. Each edge is given by the numbers of the two nodes 
connected by it. Nodes are numbered from 0 to n-1. Edges are undirected. Nodes 
have degrees of three or less. The network is not neccessarily connected. 

Input will be terminated by two values of 0 for n and m. 

Output 
======
For each test case, print the length of the longest road on a single line.

Sample Input 
============
3 2
0 1
1 2
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
0 0


Sample Output 
=============
2
12

Other related posts: