In a presidential campaign, a candidate plans to visit n towns by bicycle. He wants to visit each of the n towns exactly once. If there is a road from town i to town j , then let n(i, j ) denote the number of voters he will meet if he rides bicycle from town i to town j . The candidate would like to maximize the total number of voters he meets on the bicycle trip. Your task is to design an optimal cycling route for the candidate, i.e., a route that maximizes the total number of voters he will meet.
The candidate may use other transportation methods to travel from place to place. So the route need not be connected. However, for each of the n towns he must visit by bicycle exactly once. I.e., he must enter the town exactly once by bicycle and leave the town exactly once by bicycle. He may enter and leave the town by other means of transportation, and those trips do not count. Once he leaves town i for town j , he will finish the ride from town i to town j .
It is allowed that there is a road from i to j , but there is no road from j to i (the roads are one-way roads). If there are road from i to j , and also road from j to i, then n(i, j ) and n(j, i) maybe different.
We use an edge weighted directed graph G as a model for this problem. The n towns are the vertices of the graph. If there is a road from i to j , then connect i to j by a directed edge (i, j ). The directed edge (i, j ) has edge weight n(i, j ). In the language of graph theory, the bicycle route will be a family of vertex disjoint directed cycles that contains all the vertices of G.
For example, if there are 5 towns: 1,2,3,4,5. The directed edges are: (1, 2), (2, 3), (3, 1), (4, 5), (5, 4), (3, 4), (5, 1) with edge weights: n(1, 2) = n(2, 3) = n(3, 1) = 100 and n(4, 5) = n(5, 4) = 200 and n(3, 4) = n(5, 1) = 10. Then there are two possible bicycle routes. Route 1: 1-2-3-4-5-1. Route 2: 1-2-3-1, 4-5-4. The first route meets 420 voters, and the second route meets 700 voters. So the optimal route is Route 2.
The input file consists of a number of test cases. The first line of each test case is a positive integer n, which is the number of towns. These n towns are denoted by positive integers 1, 2, · · · , n. The next n lines are information about connecting roads between these towns. The i-th line of these n lines consists of an even number of positive integers and a 0 at the end. The first integer is a town j for which there is a road from i to j, i.e., j is an out-neighbor of i in the directed graph, and the second integer is n(i, j). The third integer is another town j′ which is an out-neighbor of i, and the fourth integer is n(i, j′), and so on. In general, the (2k − 1)th integer is a town t which is an out-neighbor of town i, and the 2kth integer is n(i, t).
The next case starts immediately after these n lines. A line consisting of a single 0 indicates the end of the input file.
Each test case has at most 100 towns. For each directed edge (i, j), n(i, j) is a positive integer less than 1000.
The output contains one line for each test case. If the required cycling route exists, then the output is a positive number, which is the total number of voters the candidate will meet on an optimal cycling route. Otherwise, the output is a letter N.
5 2 100 0 3 100 0 1 100 4 10 0 5 200 0 4 200 1 10 0 8 2 3 3 1 0 3 3 1 1 4 4 0 1 2 2 7 0 5 4 6 7 0 4 4 3 9 0 7 4 8 5 0 6 2 5 8 8 1 0 6 6 7 2 0 3 2 5 0 3 4 0 2 3 0 0
700 40 N
Migrated from old NTUJ.
NCPC2007
| No. | Testdata Range | Score |
|---|