poj1734 Sightseeing trip【最小环】

Sightseeing trip

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions:8588		Accepted:3224		Special Judge

Description

There is a travel agency in Adelton town on Zanzibar island. It has decided to offer its clients, besides many other attractions, sightseeing the town. To earn as much as possible from this attraction, the agency has accepted a shrewd decision: it is necessary to find the shortest route which begins and ends at the same place. Your task is to write a program which finds such a route. 

In the town there are N crossing points numbered from 1 to N and M two-way roads numbered from 1 to M. Two crossing points can be connected by multiple roads, but no road connects a crossing point with itself. Each sightseeing route is a sequence of road numbers y_1, ..., y_k, k>2. The road y_i (1<=i<=k-1) connects crossing points x_i and x_{i+1}, the road y_k connects crossing points x_k and x_1. All the numbers x_1,...,x_k should be different.The length of the sightseeing route is the sum of the lengths of all roads on the sightseeing route, i.e. L(y_1)+L(y_2)+...+L(y_k) where L(y_i) is the length of the road y_i (1<=i<=k). Your program has to find such a sightseeing route, the length of which is minimal, or to specify that it is not possible,because there is no sightseeing route in the town.

Input

The first line of input contains two positive integers: the number of crossing points N<=100 and the number of roads M<=10000. Each of the next M lines describes one road. It contains 3 positive integers: the number of its first crossing point, the number of the second one, and the length of the road (a positive integer less than 500).

Output

There is only one line in output. It contains either a string 'No solution.' in case there isn't any sightseeing route, or it contains the numbers of all crossing points on the shortest sightseeing route in the order how to pass them (i.e. the numbers x_1 to x_k from our definition of a sightseeing route), separated by single spaces. If there are multiple sightseeing routes of the minimal length, you can output any one of them.

Sample Input

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

Sample Output

1 3 5 2

Source

CEOI 1999

题意：

有n个点，m条带权无向边。希望找到一条路径最短的环，环上至少包含三个点，输出长度和路径。

思路：

第一次写这种最小环问题。其实本质就是要枚举节点，再枚举路径上和他直接相邻的两个节点。

在floyd算法的步骤里，外层循环k刚开始时，$d[i,j]$保存的是从$i$经过$1~k-1$中的某个节点到$j$的最短路长度。

那么$d[i,j] + g[j,k] + g[k,i]$就是一个从$i$经过$j$直接到$k$再直接回到$i$的一个环的路径，这个的最小值就是他对应的路径的最小环。

枚举每一个$k$，找到上面式子的最小值，就是整个图的最小环。

输出路径的话其实就是相当于一个dfs

注意点：

有重边，所以存的是边的最小值。

$d[i,j] + g[j,k] + g[k,i]$可能会在运算时超出int，因为可能有的两两节点之间没有边存在也就是inf

虐狗宝典阅读笔记：

对于有向图的最小环问题，可枚举起点$s = 1~n$，执行堆优化的Dijkstra算法求解单源最短路经。$s$一定是第一个被从堆中取出的节点，我们扫描$s$的所有出边，当扩展、更新完成后，令$d[s] = inf$,然后继续求解。当$s$第二次被从堆中取出时，$d[s]就是经过点$s$的最小环长度。

#include<iostream>
//#include<bits/stdc++.h>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<climits>
using namespace std;
typedef long long LL;
#define N 100010
#define pi 3.1415926535
#define inf 0x3f3f3f3f

int n, m;
const int maxn = 105;
int g[maxn][maxn], d[maxn][maxn], pos[maxn][maxn], ans;
vector<int>path;

void get_path(int i, int j)
{
    if(pos[i][j] == 0)return;
    get_path(i, pos[i][j]);
    path.push_back(pos[i][j]);
    get_path(pos[i][j], j);
}

void floyd()
{
    ans = inf;
    memcpy(d, g, sizeof(g));
    for(int k = 1; k <= n; k++){
        for(int i = 1; i < k; i++){
            for(int j = i + 1; j < k; j++){
                if(ans > (long long)d[i][j] + g[j][k] + g[k][i]){
                    ans = d[i][j] + g[j][k] + g[k][i];
                    path.clear();
                    path.push_back(i);
                    get_path(i, j);
                    path.push_back(j);
                    path.push_back(k);
                }
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(d[i][j] > d[i][k] + d[k][j]){
                    d[i][j] = d[i][k] + d[k][j];
                    pos[i][j] = k;
                }
            }
        }
    }
}

int main()
{
    while(scanf("%d%d", &n, &m) != EOF){
        memset(g, 0x3f, sizeof(g));
        memset(pos, 0, sizeof(pos));
        for(int i = 1; i <= n; i++){
            g[i][i] = 0;
        }
        for(int i = 0; i < m; i++){
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            g[u][v] = g[v][u] = min(g[u][v], w);
        }

        floyd();
        if(ans == inf){
            printf("No solution.
");
        }
        else{
            for(int i = 0; i < path.size(); i++){
                printf("%d", path[i]);
                if(i == path.size() - 1){
                    printf("
");
                }
                else{
                    printf(" ");
                }
            }
        }
    }
    return 0;
}