OJ Board

Hi,

I'm preparing a short talk about graph algorithm's problems.

Did you have a problem in which you didn't expect a graph problem behind, or which has a nice or cool solution (possibly for
teaching purposes)?

Many Thanks in advance!

of course, immeadiatly I remember about 429 - Word Transformation, there are several others, I don't remember which ones :\

Well there is one I remember:439 Knight Moves
Its about finding shortest route
for a chess knight to take between
any two point on a standard chessboard or
something very similar

Hth,

Suman

yes, and I suggest that U post some problem that can use graph to solve.....

Consider please:
10239 The Book-shelver's Problem (the shortest path)
10266 Surveying (connected components)
10265 Toroidal Chess Queens' Problem (tree rounds ???)
709 Formatting Text (the shortest path)

here are some more..

280(vertex)
459,10147 ,10397 - connectivity
10178(count the faces)

I don't know if this problem is in the problem set, I did it during the selection for the IOI...

There are some cities, and streets between them. A station must be put in every street to control it, at the entrance at one of the city linked by that street. Every street need no more than one station.

For every street linking, e.g., city A and B, find if the station must be put at the entrance of city A or city B. You must minimize the difference between the city with the most stations at its entrances and the one with the smallest one. E.G., if city A has 4 stations and city E has 3 ones, the difference is 1.

It's a rare graph problem...

Goodbye

Alessandro, Do you have its test data ?

No. I met this problem at the last contest for the selection of the IOI italian ieam, and I don't think my trainers will release the test cases. I'm sorry...

Ciao

10054 - euler problem , but j get WA

USACO 5.5 Telecowmunication(But I don't know how to solve i )

Farmer John's cows like to keep in touch via email so they have created a network of cowputers so that they can intercowmunicate. These machines route email so that if there exists a sequence of c cowputers a1, a2, ..., a(c) such that a1 is connected to a2, a2 is connected to a3, and so on then a1 and a(c) can send email to one another.

Unfortunately, a cow will occasionally step on a cowputer or Farmer John will drive over it, and the machine will stop working. This means that the cowputer can no longer route email, so connections to and from that cowputer are no longer usable.

Two cows are pondering the minimum number of these accidents that can occur before they can no longer use their two favorite cowputers to send email to each other. Write a program to calculate this minimal value for them, and to calculate a set of machines that corresponds to this minimum.

For example the network:

1*
/
3 - 2*
shows 3 cowputers connected with 2 lines. We want to send messages between 1 with 2. Direct lines connect 1-3 and 2-3. If cowputer 3 is down, them there is no way to get a message from 1 to 2.

PROGRAM NAME: telecow
INPUT FORMAT
Line 1
Four space-separated integers: N, M, c1, and c2. N is the number of computers (1 <= N <= 100), which are numbered 1..N. M is the number of connections between pairs of cowputers (1 <= M <= 600). The last two numbers, c1 and c2, are the id numbers of the cowputers that the questioning cows are using. Each connection is unique and bidirectional (if c1 is connected to c2, then c2 is connected to c1). There can be at most one wire between any two given cowputers. Computer c1 and c2 will not have a direction connection.

Lines 2..M+1
The subsequent M lines contain pairs of cowputers id numbers that have connections between them.


SAMPLE INPUT (file telecow.in)
3 2 1 2
1 3
2 3
OUTPUT FORMAT
Generate two lines of output. The first line is the minimum number of connections that can be down before terminals c1 & c2 are no longer connected. The second line is a minimal-length sorted list of cowputers that will cause c1 & c2 to no longer be connected. Note that neither c1 nor c2 can go down. In case of ties, the program should output the set of computers that, if interpreted as a base N number, is the smallest one.

SAMPLE OUTPUT (file telecow.out)
1
3

Alexander Denisjuk wrote:Consider please:
10239 The Book-shelver's Problem (the shortest path)
10266 Surveying (connected components)
709 Formatting Text (the shortest path)

Could you give me some hints about those problems?

I got AC on other problems in this thread, but I have exactly no idea about the three you listed.

117
125
793
10608
20731

and those annoying questions with all possible 4 letter combinations of {a,b,c,d} appears once in a string
like
aaaabaaac etc

here is a usefull like to both graph algos and examples of each algo:


http://www.comp.nus.edu.sg/~stevenha/pr ... raph1.html

good luck in ur talk:)