java - 将输入集放入图形拼图的数据结构中，然后求解(python 或 java)

Question

我刚刚参加了一道编程竞赛题，但我完全考砸了。我一开始就在阅读输入集时遇到了麻烦。这个问题基本上是这个谜题的变体 http://codercharts.com/puzzle/evacuation-plan但在第一行也有一个小时的组成部分(比如疏散开始后 3 小时)。是这样写的

This puzzle is a tribute to all the people who suffered from theearthquake in Japan. The goal of this puzzle is, given a network ofroad and locations, to determine the maximum number of people that canbe evacuated.

The people must be evacuated from evacuation points to rescue points.The list of road and the number of people they can carry per hour isprovided.

Input Specifications Your program must accept one and only one commandline argument: the input file. The input file is formatted as follows:the first line contains 4 integers n r s t n is the number oflocations (each location is given by a number from 0 to n-1) r is thenumber of roads s is the number of locations to be evacuated from(evacuation points) t is the number of locations where people must beevacuated to (rescue points) the second line contains s integersgiving the locations of the evacuation points the third line containst integers giving the locations of the rescue points the r followinglines contain to the road definitions. Each road is defined by 3integers l1 l2 width where l1 and l2 are the locations connected bythe road (roads are one-way) and width is the number of people perhour that can fit on the road

现在看看示例输入集

5 5 1 2 3

0

3 4

0 1 10

0 2 5

1 2 4

1 3 5

2 4 10

第一行中的 3 是附加组件，定义为自救援开始以来的小时数，在本例中为 3。

现在我的解决方案是使用 Dijisktras 算法找到每个救援节点和疏散节点之间的最短路径。现在我的问题开始于如何读取输入集。我阅读了 python 中的第一行并将值存储在变量中。但是后来我不知道如何存储节点之间的距离值以及使用什么 DS 以及如何输入它来表示 dijikstras 算法的标准实现。

所以我的问题有两个1.) 我如何接受此类问题的输入？ - 我最近在很多比赛中都遇到过这个问题，我希望我能得到一个简单的代码片段或 java 或 python 中的解释来读取数据输入集，这样我就可以将它作为图形输入到图形算法像 dijikstra 和 floyd/warshall。上述问题的解决方案也会有所帮助。

2.) 如何解决这个难题？我的算法是:

1. Find shortest path between evac points (in the above example it is 14 from 0 to 3)
2. Multiply it by number of hours to get maximal number of saves

此外，输入集的变体给出的答案是 24，我不明白。有人也可以解释一下吗。

更新:

我在给定的问题链接中得到答案是 14 - 它似乎只是节点 0 和 3 之间的最短路径。但是对于 3 小时的部分，答案是 24

更新

我明白了它是 24 - 它每小时进行一次完整的图形遍历，这就是我解决它的方法

Hour 1
Node 0 to Node 1 - 10 people
Node 0 to Node 2- 5 people
TotalRescueCount=0
Node 1=10
Node 2= 5

Hour 2
Node 1 to Node 3 = 5(Rescued)
Node 2 to Node 4 = 5(Rescued)
Node 0 to Node 1 = 10
Node 0 to Node 2 = 5 
Node 1 to Node 2 = 4
TotalRescueCount = 10
Node 1 = 10
Node 2= 5+4 = 9

Hour 3
Node 1 to Node 3 = 5(Rescued)
Node 2 to Node 4 = 5+4 = 9(Rescued)
TotalRescueCount = 9+5+10 = 24

对于这种情况来说已经够难了，对于多个疏散和救援点，我到底要如何为此编写一个 pgm？

Answer 1

这看起来像是一个网络流量问题，你可以从不同算法的链接开始解决它

http://en.wikipedia.org/wiki/Maximum_flow_problem