题目大意:给一张无向图,求这个图中的最小环并输出路径。
思路:在每次正常的Floyd更新最短路之前,先判断是否有最小环,然后再进行正常的floyd更新。如果在k更新最短路之前i和j就已经有点将他们更新,那么i->j就有一个环。然后就可以递归找出路径。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 110 #define INF 0x2a2a2a2a using namespace std; int points,edges; int map[MAX][MAX],src[MAX][MAX],cover_by[MAX][MAX]; int ans[MAX],total; int min_circle = INF; void Floyd(); void GetAns(int l,int r); int main() { cin >> points >> edges; memset(map,0x2a,sizeof(map)); for(int x,y,z,i = 1;i <= edges; ++i) { scanf("%d%d%d",&x,&y,&z); map[x][y] = map[y][x] = min(map[x][y],z); } memcpy(src,map,sizeof(src)); Floyd(); if(min_circle == INF) puts("No solution."); else for(int i = 1;i <= total; ++i) printf("%d%c",ans[i],i == total ? '\n':' '); return 0; } void Floyd() { for(int k = 1;k <= points; ++k) { for(int i = 1;i <= points; ++i) for(int j = 1;j <= points; ++j) { if(min_circle > src[i][k] + src[k][j] + map[i][j] && i != j && i != k && j != k) { min_circle = src[i][k] + src[k][j] + map[i][j]; total = 0; ans[++total] = i; GetAns(i,j); ans[++total] = j; ans[++total] = k; } } for(int i = 1;i <= points; ++i) for(int j = 1;j <= points; ++j) if(map[i][j] > map[i][k] + map[k][j]) { map[i][j] = map[i][k] + map[k][j]; cover_by[i][j] = cover_by[j][i] = k; } } } void GetAns(int l,int r) { int mid = cover_by[l][r]; if(!mid) return ; GetAns(l,mid); ans[++total] = mid; GetAns(mid,r); }