题意：一个无向图，所有边权为正，求这个无向图中的一个权值最小的环（环的权值定义为环中所有边权值的和）。要求环的顶点数至少为3个，且图中可能存在重边。
分析：这个题我最开始只有搜索的想法，后来看到了floyd的做法，才折服了，向强大的floyd致敬！ 这个题可以这么想，抛开floyd的思路，我们知道每个环中都有一个顶点标号最大的顶点（比如为k）。我们可以枚举这个顶点，枚举完这个顶点之后我们再枚举另外两个和它相邻的顶点i和j（i，j < k）。如果这个时候我们知道i到j的不经过k的最短路（设为p），那么我们就可以把边i->k，k->j和路径p组合起来，成为一个环，如果这个环的权值小于当前求出的所有环里面的最小权值的话，那么就更新一下最小值，并记录路径。
恩，这个思路看上去是挺好的，但是我们怎么求i到j的不经过k的最短路呢？想到了什么？floyd！ floyd的本质是个dp，dp[k][i][j]代表i到j的中间节点（不包括i和j）都在区间[1，k]时，i到j的最短路。floyd算法的最外层循环是个从小到大枚举k的过程，当最外层刚刚进入第k次循环的时候，我们已经得到了所有点对的dp[k-1][][]的值，也就是所有点对（i，j）的i到j的中间节点都在[1，k-1]区间的i到j的最短路，如果在这个时候我们顺便设定一下所求环中的顶点编号最大的也为k，那么我们可以根据dp[k-1][][]的值求出一个环，做法就是枚举k的相邻节点i和j（i，j < k）。这个时候dp[k-1][i][j]记录的最短路一定不包含点k，那么i->k，k->j和dp[k-1][i][j]就构成了一个环。
/*
POJ 1734
code by heifrank
*/
#include <iostream>
using namespace std;
const int MV = 105;
const int INF = 1<<30;
int G0[MV][MV], G[MV][MV], pre[MV][MV];
int path[MV];
int cnt;
void update(int a, int b, int k){
cnt = 0;
int p = b;
do{
path[cnt++] = p;
p = pre[a][p];
}while(p != a);
path[cnt++] = a, path[cnt++] = k;
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++)
G[i][j] = INF, pre[i][j] = i;
G[i][i] = pre[i][i] = 0;
}
int u, v, w;
while(m--){
scanf("%d%d%d", &u, &v, &w);
if(G[u][v] > w)G[u][v] = G[v][u] = w;
}
for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)G0[i][j] = G[i][j];
int ans = INF;
for(int k=1; k<=n; k++){
for(int i=1; i<k; i++)for(int j=i+1; j<k; j++)
if(G0[i][k] != INF && G0[k][j] != INF){
int tv = G[i][j] + G0[i][k] + G0[k][j];
if(tv < ans){
ans = tv;
update(i, j, k);
}
}
for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)
if(G[i][k] != INF && G[k][j] != INF){
int tv = G[i][k]+G[k][j];
if(tv < G[i][j])G[i][j] = tv, pre[i][j] = pre[k][j];
}
}
if(ans == INF)puts("No solution.");
else{
for(int i=0; i<cnt; i++)
printf("%d%c", path[i], i==cnt-1?'\n':' ');
}
return 0;
}
Comments