描述：
给定一行无向图，求图中一个至少包含3个点的环，环上的顶点不重复，并且要求环上的边的长度之和最小，这个问题称之为无向图最小环问题
算法：
在\(Floyd\)中,我们知道在每个外层K循环结束后,\(f[i][j]\)有着经过编号\(1\)到\(k\)之间的节点的从\(i\)到\(j\)的最短路
那么我们在第\(K+1\)个循环中先枚举起点与终点\(i,j\),寻找经过编号在\(1\)到\(k\)之间的节点的从\(i\)到\(j\)的最小环就好了
例题:
代码：
#include#include #include #include #include #include using namespace std;const int maxn=105;const int inf=999999;int f[maxn][maxn];int n,m; int x,y,z;int dis[maxn][maxn];int main(){ while(scanf("%d %d",&n,&m)!=EOF){ int ans=inf; for(register int i=1;i<=n;i++){ for(register int j=1;j<=n;j++){ dis[i][j]=f[i][j]=inf; } } for(register int i=1;i<=m;i++){ scanf("%d %d %d",&x,&y,&z); f[x][y]=f[y][x]=dis[x][y]=dis[y][x]=min(f[x][y],z); } for(register int k=1;k<=n;k++){ for(register int i=1;i
有向图上的最小环
Floyd
首先用一次Floyd,然后枚举起点\(1\)到\(i\),同时枚举中转点\(k\),只要求\(min(f[i][k]+f[k][i])\)即可
Dijsktra----《来自算法竞赛进阶指南》
枚举起点\(s\)从\(1\)到\(n\),求单源最短路径,在一次Dijsktra完成后将\(dis[s]\)设为\(inf\),下一次d[s]再次从堆中取出时就是最小环长度
特殊地
若题目中已规定了起点，上述loyd照样可用，同时有个更快用Dijsktra解决的方法.
我们正常建图后再对要求的起点建立反向边，进行两次单源最短路径，就得到了起点到其他点的最短路\(dis[]\)和其他点到起点的最短路\(f\_dis[]\)，然后求出\(min(dis[i]+f\_dis[i])\)即可
例题
注意处理点权
代码（蒟蒻只有90分）：
#include#include #include #include #include #include #include #define ll long long #define ri register intusing namespace std;const int maxn=205;const int maxm=300005;const int inf=0xfffffff;struct Edge{ int ne,to,dis;}edge[maxm],_edge[maxm];int h[maxn],num_edge=0;int _h[maxn],_num_edge=0;inline void add_edge(int f,int t,int d){ edge[++num_edge].ne=h[f]; edge[num_edge].to=t; edge[num_edge].dis=d; h[f]=num_edge;}inline void _add_edge(int f,int t,int d){ _edge[++_num_edge].ne=_h[f]; _edge[_num_edge].to=t; _edge[_num_edge].dis=d; _h[f]=_num_edge;}int g[maxn];int n,m;struct Ele{ int ver,dis; bool operator <(const Ele &b)const{ return dis>b.dis; } Ele(int x,int y){ver=x,dis=y;} Ele(){ver=dis=0;}};template inline void read(T &x){ x=0;int ne=0;char c; while(!isdigit(c=getchar()))ne=c=='-'; x=c-48; while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48; x=ne?-x:x; return ;}int dis[maxn],_dis[maxn];inline void dijsktra(){ priority_queue a; bool vis[maxn]; for(ri i=1;i<=n;i++)dis[i]=inf,vis[i]=0; dis[1]=g[1]; a.push(Ele(1,0)); while(a.size()){ int u=a.top().ver; a.pop(); if(vis[u])continue; vis[u]=1; for(ri i=h[u];i;i=edge[i].ne){ int v=edge[i].to; if(dis[v]>dis[u]+edge[i].dis){ dis[v]=dis[u]+edge[i].dis+g[v]; if(!vis[v])a.push(Ele(v,dis[v])); } } }// for(ri i=1;i<=n;i++)printf("%d\n",dis[i]); return ;}inline void _dijsktra(){ priority_queue b; bool vis[maxn]; for(ri i=1;i<=n;i++)_dis[i]=inf,vis[i]=0; _dis[1]=g[1]; b.push(Ele(1,0)); while(b.size()){ int u=b.top().ver; b.pop(); if(vis[u])continue; vis[u]=1; for(ri i=_h[u];i;i=_edge[i].ne){ int v=_edge[i].to; if(_dis[v]>_dis[u]+_edge[i].dis){ _dis[v]=_dis[u]+_edge[i].dis+g[v]; if(!vis[v])b.push(Ele(v,_dis[v])); } } }// for(ri i=1;i<=n;i++)printf("%d\n",_dis[i]); return ;}inline void solve(){ int mi=inf; for(ri i=2;i<=n;i++){ if(dis[i]==inf||_dis[i]==inf)continue; mi=min(mi,dis[i]+_dis[i]-g[1]-g[i]); } if(mi!=inf)printf("%d\n",mi); else puts("-1"); return ;}int main(){ int u,v,d; read(n),read(m); for(ri i=1;i<=n;i++){ read(g[i]); } for(ri i=1;i<=m;i++){ read(u),read(v),read(d); add_edge(u,v,d); _add_edge(v,u,d); } dijsktra(); _dijsktra(); solve(); return 0;}