Tour
Time Limit: 3000/1000 MS (Java/Others)Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 725Accepted Submission(s): 363
Problem Description
In the kingdom of Henryy, there are N (2 <= N <= 200) cities, with M (M <= 30000) one-way roads connecting them. You are lucky enough to have a chance to have a tour in the kingdom. The route should be designed as: The route should
contain one or more loops. (A loop is a route like: A->B->……->P->A.)
Every city should be just in one route.
A loop should have at least two cities. In one route, each city should be visited just once. (The only exception is that the first and the last city should be the same and this city is visited twice.)
The total distance the N roads you have chosen should be minimized.
Input
An integer T in the first line indicates the number of the test cases.
In each test case, the first line contains two integers N and M, indicating the number of the cities and the one-way roads. Then M lines followed, each line has three integers U, V and W (0 < W <= 10000), indicating that there is a road from U to V, with the
distance of W.
It is guaranteed that at least one valid arrangement of the tour is existed.
A blank line is followed after each test case.
Output
For each test case, output a line with exactly one integer, which is the minimum total distance.
Sample Input
1
6 9
1 2 5
2 3 5
3 1 10
3 4 12
4 1 8
4 6 11
5 4 7
5 6 9
6 5 4
Sample Output
Source
刚开始看题表示完全木有思路。
后来看到别人用匹配。然后想了下,觉得有道理,就写了下,还好,1Y。
不过个人感觉还是没有领悟到精髓所在。。恩
先把代码贴出来,在仔细想想。恩
我的代码:
分享到:
相关推荐
ACM/ICPC 2010年多校联合第十场第九题的解题报告及代码,AC代码有三个,最好的是src
HDU2013暑期多校联合训练第一场0723-解题报告和标程
2017hdu多校联合训练第一场标程及数据
HDU图论题目分类
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
2014 Multi-University Training Contest 1多校联合赛标程和部分数据。
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
2019 Multi-University Training Contest 4(2019hdu多校第五场数据与标程),欢迎大家下载
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个...
此程序为hdu的acm2010题,就是解决水仙花数问题
HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用
HDU2000至2099题的题目以及AC代码(含思路) 适合刚刚接触ACM的同学哦~ emmmm凑字
有2019 Multi-University Training Contest 4,hdu多校第四场的题解,数据标程,有需要的可以下载哦
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
此乃2012多校联赛第五场的题目+数据+题解+标程