Problem 1009 Jogging Trails

来源:http://acm.fzu.edu.cn/problem.php?pid=1009

Problem Description
Gord is training for a marathon. Behind his house is a park with a large network of jogging trails connecting water stations. Gord wants to find the shortest jogging route that travels along every trail at least once.Input consists of several test cases. The first line of input for each case contains two positive integers: n <= 15, the number of water stations, and m < 1000, the number of trails. For each trail, there is one subsequent line of input containing three positive integers: the first two, between 1 and n, indicating the water stations at the end points of the trail; the third indicates the length of the trail, in cubits. There may be more than one trail between any two stations; each different trail is given only once in the input; each trail can be travelled in either direction. It is possible to reach any trail from any other trail by visiting a sequence of water stations connected by trails. Gord’s route may start at any water station, and must end at the same station. A single line containing 0 follows the last test case.

For each case, there should be one line of output giving the length of Gord’s jogging route.

1
2
3
4
5
6
7
8
9
10
Sample Input
4 5
1 2 3
2 3 4
3 4 5
1 4 10
1 3 12
0
Sample Output
41

思路:第一次看到这道题..想到的就是欧拉图,但是我想到的确是欧拉图入度出度为奇数只能有一组….然后想了一会没想出来,百度看了下大神们的blog,结果却是填补欧拉图,使其所有的度变为偶度(明显我离散课没学好,我只学到了有什么东西能做什么事,但是具体怎么做就没去深究….) 然后我决定把所有的奇度提取出来,跟消消乐一样 每2个奇度消除变成2个偶度,这样又遇到了一个问题.就是如果奇度A 到达奇度B的最短路径有可能是A->C->B(这样确实可以,因为C的度加了2 ,任然是偶度)这样的路径,所以还得把偶度也加入计算,灵光一闪..想起了数据结构的图论里面有一个关于任意两点之间最短路径的算法,立马翻书查看(只知道有这个东西,不知道怎么写…还是不认真…),看了一会,啪啪啪啪代码一阵乱敲,提交->错误,提交->错误,提交->错误,提交->错误,改了7-8次代码吧,放弃,上床睡觉,百度看看大神怎么写的,结果乍一看,我就跳了起来….我把输入部分

1
2
1 2 3
1 2 4

这样的情况忽略了,立马起身下床,对着电脑啪啪啪啪一阵输出..提交 AC……终于过了…
目前为止写的比较难的代码了…..这好像就是 福大oj的起步题……哎,还是得练 .
代码比较乱,还没整理,就是想到什么写什么,估计可以修减很多地方,有空再修吧,先附上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <map>
using namespace std;
int smap[17];
int nmap[17];
int map1[17][17];
int jk = 0;
int n, m;
int sigh = 0;
int sum=0;
int sum1 = 0;
int mixxx = 9999999;
map<int, int> gggg;
int getleft(int ll) { return 1 << ll; }
void makeShortPath() {
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
if (i == j) { map1[i][j] = 0; }
else {
for (int k = 1; k <= n; k++)
{
if (((map1[i][j] > map1[i][k] + map1[k][j])|| map1[i][j]==0)&& (map1[i][k] * map1[k][j]) != 0) {
map1[i][j] = map1[i][k] + map1[k][j];
map1[j][i] = map1[i][j];
}
}
}
}
}
}
int s(int flag) {
if (flag == 0) {
return 0;
}
map<int, int>::iterator it = gggg.find(flag);
if (it!= gggg.end()) {
return it->second;
}
int max111000 = 9999999;
for (int i = 0; i < jk; i++) {
int sk = 0,j;
for (j= 0; j < jk; j++) {
if (smap[j] != 0) {
sk = j; break;
}
}
for (int j = sk+1; j < jk; j++) {
if (smap[j] != 0) {
int tt, qq;
tt = smap[sk];
qq = smap[j];
smap[sk] = 0;
smap[j] = 0;
int sum2=s(flag^ getleft(tt)^ getleft(qq))+ map1[tt][qq];
if (sum2 < max111000)max111000 = sum2;
smap[sk] = tt;
smap[j] = qq;
}
}
}
gggg.insert(pair<int, int>(flag, max111000));
return max111000;
}
int main(int argc, char *argv[]) {
while ((cin >> n) && n != 0) {
jk = 0;
sigh = 0;
sum = 0;
sum1 = 0;
mixxx = 9999999;
cin >> m;
gggg.clear();
memset(map1, 0, sizeof(int) * 17 * 17);
memset(nmap, 0, sizeof(int) * 17);
memset(smap, 0, sizeof(int) * 17);
for (int i = 0; i < m; i++) {
int a, b, len;
cin >> a >> b >> len;
sum += len;
nmap[a]++;
nmap[b]++;
if (len < map1[a][b] || map1[a][b] == 0) {
map1[a][b] = map1[b][a] = len;
}
}
for (int i = 1; i <= n; i++) {
if (nmap[i] % 2 != 0) {
smap[jk++] = i;
sigh = sigh | (getleft(i));
}
}
makeShortPath();
int sssss=s(sigh);
map<int, int>::iterator it = gggg.find(sigh);
cout << it->second + sum << endl;
}
return 0;
}