首页 > ACM题库 > HDU-杭电 > HDU 3423-Subway upgrade-动态规划-[解题报告]HOJ
2014
03-23

HDU 3423-Subway upgrade-动态规划-[解题报告]HOJ

Subway upgrade

问题描述 :

As we all know, one of the most important inventions for modern-day public transportation is the subway, which brings much convenience to our daily-life and saves us from the congested traffic.
However, to hold the next ACM regional contest, you, as the mayor of city X, decided to upgrade the subway system of that city. There are some stations and roads in the city now, any road has a cost. To save money, you decided not to construct every road, but to make sure that there exist a path between every two stations.
Sorry, the mission isn’t completed. You know, there are n stations in the city,some contestants visit other stations regularly to admire some so-called big cows. Being naturally averse to spending hours each day on commuting, you should help them to find a place to live for which the total travel time is minimal.
Every road has an ID, from 1 to m. If there are multiple approaches leading to the same minimal cost, the mayor prefers the one of which road IDs selected holds the smallest lexicographic order. For instance, rebuilding ID ( 1 3 5) and ID (2 4 5) will both ensure the minimum cost,the mayor will choose the former one.

输入:

First,a number t,indicating the number of the testcases.
For every testcase, there is a number n and m,n(1<=n<=50000) indicating the number of cities,whereas m (0<=m<=500000) indicating the number of roads.
then m lines follow each lines contains three integers a,b,c.(1<=a,b<=n&&a!=b,1<=c<=10000)which means there is a road from a to b whose cost is c.

输出:

First,a number t,indicating the number of the testcases.
For every testcase, there is a number n and m,n(1<=n<=50000) indicating the number of cities,whereas m (0<=m<=500000) indicating the number of roads.
then m lines follow each lines contains three integers a,b,c.(1<=a,b<=n&&a!=b,1<=c<=10000)which means there is a road from a to b whose cost is c.

样例输入:

3
3 3
1 2 10
2 3 20
3 1 15
3 1
1 2 15
2 1
1 2 15

样例输出:

25
1
50
Poor mayor.
15
1 2
30


Hint:
In the first sample we use road 1 and 3 ,the minimus cost is 10+15=25
and we get a new graph 3-1-2,city 1 is the best answer ,2*10+2*15=50
Whereas the third, we can't get city 1,2,3 connected.
In the last, we choose the road 1,the minimus cost is 15
and we get a new graph 1-2,both city 1 and city 2 are the best answer ,2*15=30

【题目链接】http://acm.hdu.edu.cn/showproblem.php?pid=3423

【题目大意】

        给n个城市,m条计划修的路,n<=50000, m<=500000,要求一个最小代价,使得任意两个城市可以到达,然后问有没有那样一个中心点,使得其他的点到那个点的距离之和最小,将这些点全部输出。

【分析】

        hdoj去年6月月赛题,昨天被我挂比赛了,发现纯粹水题大战,到现在差两题AK,orz一个是spfa+最大流不会,还有一个是貌似神秘的数论不想看。貌似大家很膜拜出题人,Discuss里有什么言语之类。。。

        首先求最小生成树,考虑到数据范围大,必须用Kruskal算法(不会的可以查看我之前的博客),注意题目要求是按边的id来选路,我还当是按city的编号来写,结构体里排序开始错了。。。在求MST的时候便用邻接表把边存好。

        接下来DP部分,  开始纠结戴牛的意图,后来结合数据还是确定了,距离按往返算,且按点到点算。   然后想n次DFS,发现n太大,于是乎觉得可以两遍DFS分别预处理。

//num[i]:以i为根的子树的节点个数;

DFS1:

          //f1[i]:   以i为根的子树上所有点到i的距离之和; f1[u]+= f1[v]+ num[v]* (ptr->w);

          这里通过递归实现,由叶节点向上递归到根;根可以任意假设,我假设是1;

DFS2:

         //f2[i]:   所有i上方的点(都通过其父节点到达i)到i的距离之和;

         f2[v]= f2[u]+ (f1[u]-f1[v]-num[v]*w)+ (n-num[v])* w;   //画个图很容易明白的。

         这里直接从根往下传就可以。

具体见代码, 我都稍微有注释,如果发现看不懂是因为你树形DP题没有多做。。。

代码刷进第一版了, orz最近好多题都刷进了。。。

【代码】

先这样贴  百度不让贴那么长的代码。。。

http://fayaa.com/code/view/21109/

参考:http://hi.baidu.com/yimaolionel/item/13d8c235e3a4a9da6d15e936


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  3. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。