通过别人的数据搞了好久才成功,果然还是不够成熟
做题目还是算法不能融会贯通
大意即找出图中至少3个顶点的环,且将环中点按顺序输出
用floyd算法求最小环
因为floyd算法求最短路径是通过中间量k的增加而更新的
算法流程:
对于k,我们知道利用floyd算法求出任意两点i,j最短距离,仅通过路径i-()-j,其中()中的节点编号均<=k-1
可以这样证明:
设最小环上最大点的编号为k0;则当k=k0时,对于任意与k0相接两点i,j两者
1.对于环的剩下一部分必然是i到j的最短路径,因为最佳
2.最短路径必然是通过{1,...,k-1},否则该最小环最大编号必然大于k,故ans=f[i][j]+Graph[i][k]+Graph[j][k] (f[i][j]表示当前通过前k-1点为中间路径的i-j的最短路径)
故通过枚举k,取ans=min(ans,f[i][j]+Graph[i][k]+Graph[j][k]) 其中(i,j<k) 必能找到
而环顺序只需通过计算每次更新f[i][j]时的k记录pre[i][j]=k,之后通过递归即可得到,
需要注意的是:每次更新ans时就要将路径记录下来,不然之后可能路径会更新时被改变,这个改变可不代表路径还会缩短,首先要明白该算法必然能够求出最小环,故若求出最小环后可能之后缩短路径是会重边,即比如i到j的距离通过k后变短了,可是是重边得来的没有意义
#include#include #include int f[105][105],pre[105][105],Graph[105][105],ans,a[1000];const int maxn=100000000;int print(int i,int j){ if (pre[i][j]==0) return 0; print(i,pre[i][j]); a[++a[0]]=pre[i][j]; print(pre[i][j],j); return 0;}int main(){ int i,j,k,l,n,m; while(1){ scanf("%d",&n); if (n==-1) break; for(i=1;i<=n;i++) for(j=1;j<=n;j++){ f[i][j]=maxn; Graph[i][j]=f[i][j]; } memset(pre,0,sizeof(pre)); ans=maxn; scanf("%d",&m); for(i=1;i<=m;i++){ scanf("%d%d%d",&j,&k,&l); if(f[j][k]>l) {f[j][k]=l;Graph[j][k]=l;} if(f[k][j]>l) {f[k][j]=l;Graph[k][j]=l;} } for(k=1;k<=n;k++){ for(i=1;i<=k-1;i++) for(j=1;j<=k-1;j++) if(i!=j) if(ans>f[i][j]+Graph[i][k]+Graph[j][k]){//此处不能用f[][]代替Graph[][] 容易举出实例 ans=f[i][j]+Graph[i][k]+Graph[j][k]; a[0]=0; a[++a[0]]=i; print(i,j); a[++a[0]]=j; a[++a[0]]=k; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=k&&j!=k&&i!=j) if(f[i][j]>f[i][k]+f[k][j]){ f[i][j]=f[i][k]+f[k][j]; pre[i][j]=k; pre[j][i]=k; } } if(ans