| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions:8588 | Accepted:3224 | Special Judge | ||
Description
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
Output
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
题意：
有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 = ;
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] == )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 = ; k <= n; k++){
for(int i = ; i < k; i++){
for(int j = i + ; 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 = ; i <= n; i++){
for(int j = ; 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, , sizeof(pos));
for(int i = ; i <= n; i++){
g[i][i] = ;
}
for(int i = ; 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.\n");
}
else{
for(int i = ; i < path.size(); i++){
printf("%d", path[i]);
if(i == path.size() - ){
printf("\n");
}
else{
printf(" ");
}
}
}
}
return ;
}