| Time Limit: 1000MS | Memory Limit: 65536K | |||
| Total Submissions: 5590 | Accepted: 2151 | Special Judge | ||
Description
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
[Submit] [Go Back] [Status] [Discuss]
网上的题解都是用floyd做出来的，用floyd最短路算法判断是否有环，但是我感觉dfs足可以解决这道题
下面的是我的代码和题解，后面我还会贴上网上大牛用floyd写的算法
dfs：以边为核心，边上的两个点一个为起点，一个为终点，开始进行dfs搜索。每次从起点出发，如果找到终点并且路程变小就记录下路径，在后输出最短路的路径即可
如过ans的值和起始值一样的话，就相当于没有环出现，那么输出那个字符串就可以了
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; const int inf=9999999; int n,m; int Map[110][110]; int head[110]; int temp; bool vis[110]; int a[110]; int start ,end; int ans; bool judge; int t; int cnt; int ans_num; void dfs(int u,int node,int dis){ if(u==end){ if(dis<ans){ ans=dis; for(int i=0;i<node;i++) a[i]=head[i]; a[node]=u; ans_num=node; } return ; } head[node]=u; for(int i=1;i<=n;i++){ if(!Map[u][i]||vis[i]) continue; vis[i]=true; if(dis+Map[u][i]<ans) dfs(i,node+1,dis+Map[u][i]); vis[i]=false; } return; } int main(){ while(scanf("%d",&n)!=EOF){ if(n==-1) break; memset(Map,0,sizeof(Map)); scanf("%d",&m); int u,v,w; for(int i=0;i<m;i++){ scanf("%d%d%d",&u,&v,&w); if(!Map[u][v]){ Map[u][v]=w; Map[v][u]=w; } else{ if(w<Map[u][v]){ Map[u][v]=w; Map[v][u]=w; } } } ans=inf; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ if(Map[i][j]==0) continue; memset(vis,false,sizeof(vis)); t=Map[i][j]; Map[i][j]=0; Map[j][i]=0; start=i; end=j; vis[i]=true; dfs(start,0,t); Map[i][j]=t; Map[j][i]=t; } if(ans!=inf){ for(int i=0;i<=ans_num;i++) printf("%d%c",a[i],i==ans_num?‘\n‘:‘ ‘); } else printf("No solution.\n"); } return 0; }
floyd算法代码
给出一张无向图，求一个最小环并输出路径。
说说我的感觉：
包含点 i 和点 j 的最小环，我们可以看成是 i 到 j 之间的最短路和次短路的组合，通过 floyd 可求任意两点之间的最短距离，那么我们只要找到最短路径外的一条最短路来保证 i 和 j 之间可达即可。在做 floyd 循环的同时，我们以 环权值 最小（最短路权值+次短路权值=最小环权值）为标准，一直更新每个点的前驱，也就是记录 i 到 j 的最短路径，以及，能够松弛 i 和 j 的点 k （k 不在 i 到 j 的最短路径中）中代价最小的那个（也就是 i 到 j 之间的次短路），然后按环的自然顺序输出即可。
代码中也注释的很详细了：
#include<cstdio> #include<cstring> #define find_min(a,b) a<b?a:b const int N = 101; const int INF = 0x7ffffff; int mat[N][N],dist[N][N],pre[N][N],path[N],n; int main() { int i,j,k,m,a,b,c; int num; while(~scanf("%d%d",&n,&m)){ for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ mat[i][j]=dist[i][j]=INF; pre[i][j]=i; } } while(m--){ scanf("%d%d%d",&a,&b,&c); mat[a][b]=mat[b][a]=dist[a][b]=dist[b][a]=find_min(mat[a][b],c); } int min=INF; for(k=1;k<=n;k++){//最短路径外一点将最短路首尾链接,那么就得到一个最小环 for(i=1;i<k;i++){ for(j=i+1;j<k;j++){ //求最小环不能用两点间最短路松弛,因为(i,k)之间的最短路,(k,j)之间的最短路可能有重合的部分 //所以mat[][]其实是不更新的,这里和单纯的floyd最短路不一样 //dist[i][j]保存的是 i 到 j 的最短路权值和 int tmp=dist[i][j]+mat[i][k]+mat[k][j];//这里 k 分别和 i 还有 j 在mat中直接相连 if(tmp<min){ min=tmp; num=0; int p=j; while(p!=i){//回溯 path[num++]=p; p=pre[i][p];//pre[i][j]表示 i 到 j 最短路径上 j 前面的一个点 } path[num++]=i; path[num++]=k; } } } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(dist[i][j]>dist[i][k]+dist[k][j]){ dist[i][j]=dist[i][k]+dist[k][j];//dist[][]保存两点间最短距离 pre[i][j]=pre[k][j]; } } } } if(min==INF)puts("No solution."); else{ printf("%d",path[0]); for(i=1;i<num;i++) printf(" %d",path[i]); puts(""); } } return 0; }
poj 1734 Sightseeing trip判断最短长度的环
原文：http://www.cnblogs.com/13224ACMer/p/4839478.html