| Time Limit: | 1000ms |
Memory Limit: | 64000KiB |
| Accepted: | 0 |
Submitted: | 0 |
EVIL EYE
BOI 98 Day 2 Problem 2
Evil Eye
An ornament is made up of beads (called 'evil eyes') tied together with strings. A piece of string connects two beads and a bead can be attached to one or more strings. Each piece of string is colored in a certain way: one half of the string is pink and the other half is yellow. The lengths of the strings may not be the same. The ornament is meant to be hung on a wall. Hung properly, it takes the shape of a straight vertical line so that every piece of string is tight (thanks to gravity) with its pink part up and yellow part down. The beads are small enough, so we assume that two or more beads can occupy the same position in the vertical formation of the ornament. Any bead can be pinned on the wall. Pinning an arbitrary bead is enough to hold up the whole ornament -though this might not be a proper installation.
You receive an ornament as a present and you want to install it properly. You are assured by the manufacturer of the ornament that this can be done. You are allowed to pin any number of beads. When you complete the installation properly, what is the ordering of the beads from top to bottom?
Input
The input will be a text file named eye.inp.
The beads are numbered by integers 1 through B consecutively (1 <= B <= 200). The length Li,j of the piece of string connecting the bead i and bead j will be an integer (1 <= Li,j<= 10). We let S be the number of strings in the ornament.
The first line of the input file contains the integer S, which is also the number of the lines that follow. Each of the following S lines has three numbers, i, j and Li,j in this order, each separated by one blank. These three numbers represent a string connecting the bead i and bead j with length Li,j such that bead i is attached to the pink end and bead j to the yellow end of the string.
Output
The output must be an ordering of the beads from top to bottom after the ornament is installed properly.
On each line of the output there must be the number(s) of the bead(s) occupying the same position in the ordering. The ordering of numbers within the same line is not important. The first line of the output must have the number(s) of the topmost bead(s), and so on. Each of the numbers on an output line must be separated by one blank.
Your output must be a text file to be named eye.out.
Sample Input
9
1 2 3
2 3 5
2 7 1
4 5 4
5 6 1
5 9 1
6 7 1
7 8 3
9 8 4
Sample Output
4
1
5
2 6 9
7
8
3
Remark
Here is the picture of the example:
SubmitStatistics |
