文理学院程序设计在线练习


小明的旅游计划

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 11   Accepted Submission(s): 2
Problem Description

小明奶奶所在的镇上有好多风景名胜,由于常常给别人做向导,奶奶早就准备了一幅详细的导游图,图上画出了整个镇子上的N个景点(景点编号为0~N-1),还有连接这些景点的M条道路。

今年春节,小明去奶奶家做客,并打算好好欣赏一下那里的美景。到了那里,小明发现景点虽美,但景点之间的道路更是风光无限,美不胜收,因此他改变了自己的计划,除了欣赏景点外,还希望将这些道路也都走上一遍。

简单来说,就是选择某个景点作为起点,走遍全部的道路(每条路只走一遍,不能重复),且保证走遍全部景点,最后回到起点。顺便说下,若你听说过一笔画问题,应该对这个问题不会陌生,事实上这也是一个欧拉图。

拿到地图后的小明还是犹豫了,考虑到道路信息很复杂,为了不至于太扫兴而不能成行,他对原先的要求稍稍做了调整,具体如下:
1)对出发点限制为0号景点,结束位置可以任意。
2)在确保走遍所有道路的前提下, 最多允许某 一条 道路可以走两次

即使这样,要看出是否存在一种走法满足他的要求还真不是一件简单的事,因此他请你编个程序帮帮他。

针对小明的要求,请你帮他判断是否存在这样的走法,若存在这样的走法,则计算至少需要行走多少路程才能满足要求。

为了帮助说明,下面给出一些例子(图中没有标出道路的长度)。其中,全部道路只走一次就可达到要求的有图1、图2、图3;有一条道路必须走二次才可达到要求的有图4、图5、图7;无法达到要求的有图6、图8。


Input

输入数据首先包含一个整数T (1<=T<=40), 表示测试数据的组数,然后是T组测试数据。
每组测试的第一行包含两个整数N和K,(2<=N<=3000,0<=M<=10000),分别表示景点总数和道路总数。
然后是M行数据,每行3个整数x,y,z (0<=x,y<=N-1,0<z<=100000)依次表示景点x和景点y之间有一条可双向行走的道路,道路长度是z。

Output

对于每组测试,若存在这样的走法,输出至少需要行走的路程。若不存在满足条件的走法,则输出“no”。

Sample Input
5
3 3
0 1 10
1 2 20
0 2 30
3 4
0 1 10
1 2 20
0 2 30
1 0 40
3 1
0 1 10
3 2
1 0 10
2 0 20
4 5
0 1 10
0 3 20
1 3 30
2 1 40
2 3 10
Sample Output
60
100
no
40
120
Hint

测试数据量大,请考虑输入效率。
通过图(无向图或有向图)中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路,通过图中所有边一次且仅一次、行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图(Euler Graph),具有欧拉通路而无欧拉回路的图称为半欧拉图。(摘自百度百科)

Author

flx

Source

usx第七届程序设计竞赛