2010年02月10日星期三.sgu185
ALGO:dijkstra + 流
求兩條沒有相同邊的最短路。
直覺的想法是求一條，然后把這條相關(guān)的刪掉，再求另外一條
但是這種想法是不正確的。
引用
http://www.answeror.com/archives/28474 的一組數(shù)據(jù)來說明這個問題
6 7
1 2 1
1 3 1
2 4 1
3 4 1
3 5 1
4 6 1
5 6 1
如果第一次求出的最短路是1-3-4-6, 那么第二條最短路就不存在了, 但是實際上有兩條最短路,
即1-3-5-6和1-2-4-6.
所以需要調(diào)整，調(diào)整的思想讓我們想到了流。
保留圖中所有能構(gòu)成任何一條最短路的邊，將所有邊的容量設(shè)為1. 然后對這個圖求兩次增廣路。
由于容量的限制，所以求得的兩條最短路一定是沒有公共邊的，這時按照流的方向，輸出這兩條
路徑即可。
注意：不要按照增廣時的頂點順序輸出最短路，這樣是不對的，同樣可以使用上面的那組數(shù)據(jù)，
如果先增廣的是 1-3-4-6這條路徑的話，那么輸出的結(jié)果就會不正確了。 我就是這么wa@test 20 好久的。
1
2 const int N = 401;
3 const int inf = 1 << 20;
4 int dis[N],vis[N],n,m;
5 int g1[N][N],g2[N][N],p[N],f[N][N];
6
7 bool dijkstra()
8 {
9 int i,j,k;
10 memset(vis,0,sizeof(vis));
11 dis[1] = 0,vis[1] = true;
12 for (i = 2;i <= n;i++) {
13 dis[i] = g1[1][i];
14 }
15 for (k = 2;k <= n;k++) {
16 int min = inf,idx = 1;
17 for (i = 2;i <= n;i++) {
18 if (dis[i] < min && !vis[i]) {
19 min = dis[i],idx = i;
20 }
21 }
22 if (idx == 1) { break; }
23 vis[idx] = true;
24 for (i = 1;i <= n;i++) {
25 if (dis[i] > min + g1[idx][i]) {
26 dis[i] = min + g1[idx][i];
27 }
28 }
29 }
30 for (i = 1;i <= n;i++) {
31 for (j = 1;j <= n;j++) {
32 if (dis[i] + g1[i][j] == dis[j]) {
33 g2[i][j] = 1;
34 }
35 }
36 }
37 return dis[n] != inf;
38 }
39
40 bool bfs()
41 {
42 memset(vis,0,sizeof(vis));
43 memset(p,0,sizeof(p));
44 queue<int> que;
45 que.push(1),vis[1] = true;
46 while (!que.empty()) {
47 int u = que.front(); que.pop();
48 for (int v = 2;v <= n;v++) {
49 if (!vis[v] && g2[u][v]) {
50 p[v] = u,vis[v] = true;
51 if (v == n) {
52 for (v = n;v != 1;v = p[v]) {
53 u = p[v];
54 g2[u][v] --;
55 g2[v][u] ++;
56 if (f[v][u] > 0) {
57 f[v][u]--;
58 }else {
59 f[u][v] ++;
60 }
61 }
62 return true;
63 }
64 que.push(v);
65 }
66 }
67 }
68 return false;
69 }
70
71 void pr(int u)
72 {
73 if (u == n) {
74 printf("%d\n",u);
75 return;
76 }
77 for (int i = 1;i <= n;i++) {
78 if (f[u][i] > 0) {
79 f[u][i] --;
80 printf("%d ",u);
81 pr(i);
82 return ;
83 }
84 }
85 }
86
87 bool EK()
88 {
89 if (bfs() && bfs()) {
90 pr(1), pr(1);
91 return true;
92 }
93 return false;
94 }
95
96
97 int main()
98 {
99 int i,j,a,b,c;
100 scanf("%d%d",&n,&m);
101 for (i = 1;i <= n;i++) {
102 for (j = 1;j <= n;j++) {
103 g1[i][j] = inf;
104 }
105 }
106 for (i = 0;i < m;i++) {
107 scanf("%d%d%d",&a,&b,&c);
108 if (g1[a][b] > c) {
109 g1[a][b] = g1[b][a] = c;
110 }
111 }
112 if (!dijkstra() || !EK()){
113 printf("No solution\n");
114 }
115 return 0;
116 }
117