Algorithm 版 (精华区)

发信人: sigmod (sigmod), 信区: Algorithm
标  题: 《程序员》杂志2001年第11期程序擂台赛题目
发信站: 哈工大紫丁香 (2001年11月14日12:17:05 星期三), 站内信件

2001年第11期题目
骆驼商队
背景描述
在一片古老的大地上，虽然商业已经非常繁荣，但是那里的人们仍然延续着古老的交易方
式。他们牵着骆驼在城市之间往来奔波，贩运成批的商品，换来一袋袋的金币。
这片大陆上有N个城市，编号为1……N。在一些城市之间有路可通，有路就有商队。但是在
不同的城市之间经商所得的收益不同，在下面的这个N=4的例子中，在城市1和城市2之间进
行一次交易可以获得40枚金币，在城市2和3之间交易一次可以获得50枚金币，等等。
在任意两个城市之间，这样的交易只能进行一次。因为你第二次贩运你的商品时，人们对
它们就不会感兴趣了。
现在你只身来到这个大陆上，用有限的资金在每个城市中购买了1支商队。你需要想办法让
你的这N支商队给你带来最大的经济收益。
任务说明
给出这个大陆的地图和每两个城市之间的贸易值（如果这两个城市之间有路可通的话），
你需要指挥你的N支商队进行一次经商，使得这N支商队在这次经商中获得的总收益最大。
注意：你的每支商队只能进行一次交易，即它们只能从它们所在的城市到达一个相邻的城
市。当然，它们也可以不进行任何交易。
输入数据
输入文件(trade.in)的第一行有两个整数N（1≤N≤100）、M（M≥0），分别表示这个大陆
上的城市数和道路数。
接下来有M行，每行包括三个整数i、j（1≤i,j≤N且i≠j）、v(1≤V≤10000)，表示一条
道路的信息。其中i和j表示这条路在城市i和城市j之间，v表示沿着这条路进行一次交易所
得的收益。i和j的顺序是无关的，并且任意两个城市之间最多存在一条路。
输出数据
你的输出文件(trade.out)应该只有一行，包含N个整数。其中第k个整数表示你在城市k中
的商队将要前往哪个城市进行交易（如果这支商队进行交易的话）或者为0（如果这支商队
不进行任何交易）。
输入输出样例
trade.in        trade.out       样例图示
4 5              2 3 1 2
1 2 40
1 3 30
2 3 50
2 4 30
3 4 20





最大收益：40+50+30+30=150
注意
本题的解不一定是唯一的。即对于一个测试数据，可能有多种经商方案使总收益最大。在
这种情况下，你只要输出最优方案中的任意一种即可。 

--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]