最小环模板

栗子（jsdhwdmaX)
2026-01-31 10:19:33
发布于：四川
0阅读
0回复
0点赞
//最小环模板 
//洛谷P6175 
#include<iostream>
#include<string.h>
using namespace std;

const int inf = 1e8; 
const int maxn = 110; 

//mp[i][j]:存储原图中i和j之间的直接边权
//dis[i][j]:存储Floyd过程中i到j的最短路径长度 
int mp[maxn][maxn];
int dis[maxn][maxn];

int main(){
    //n节点数 m边数
    int n,m,u,v,w;
    cin>>n>>m;

    //初始化原图邻接矩阵mp：
    //点i到自身的边权默认为0
    //不同节点间初始化为无穷大 
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(i != j){//非自身,初始不可达
                mp[i][j] = inf;
            }
        }
    }

    //读入并更新 
    for(int i=1;i<=m;++i){
        cin>>u>>v>>w; //u起点 v=终点 w=边权
        mp[u][v] = w;       //无向边:u到v的直接边权
        mp[v][u] = w;       //无向边:v到u的直接边权(双向建边)
    }

    //初始化最短路径矩阵dis(初始时dis等于原图mp)
    memcpy(dis,mp,sizeof dis);

    //初始化最小环长度为无穷大
    int ans = inf;

    //Floyd-Warshall核心循环:枚举中间节点k
    //核心思想：k是环上的“最后一个节点”，先统计经过k的环长度，再更新最短路径
    for(int k=1; k<=n; ++k){ // k：枚举环的闭合节点（中间节点）
        // 6.1 统计“以k为闭合节点”的环的长度，找到当前最小环
        //dis[i][j]是不经过k的最短路径
        //环的构成:i到j(不经过k的最短路径)+j到k(直接边)+k到i(直接边)
        for(int i=1;i<k;++i){         //i:环的第一个节点(小于k)
            for(int j=i+1;j<k;++j){   //j:环的第二个节点[条件:大于i,小于k(避免重复统计)]
                //更新最小环长度[公式:当前环长度 = i到j的最短路径+i到k的直接边+k到j的直接边] 
                ans = min(ans, dis[i][j] + mp[i][k] + mp[k][j]);
            }
        }

        //Floyd松弛操作(以k为中间节点(中介节点),更新所有i到j的最短路径)
        //此时dis[i][j]已排除k,更新后dis[i][j]会包含经过k的最短路径
        for(int i=1;i<=n;++i){         //枚举起点
            for(int j=1;j<=n;++j){     //枚举终点
                //松弛:(条件：i到k+k到j的路径,比i到j的当前最短路径更短)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }

    //判断是否有环 
    if(ans == inf){ //若最小环长度仍为,则无环
        cout << "No solution." << endl;
    }
    else{//找到最小环
        cout << ans << endl;
    }

    return 0;
}
有帮助，赞一个
去预览
0/2000
这里空空如也
热门讨论
