poj 1734(无向图的最小环）

约定不等于承诺〃 2021-11-16 08:31 249阅读 0赞

## 题意：n个点，m条边的加权无向图，求其中的最小环，并输出路径。 ##

## 分析：考察对Floyd的理解，详见《算法竞赛进阶指南》P361-362，书中也提到了有向图最小环的解法。 ##

## 代码： ##

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    using namespace std;
    int a[310][310], d[310][310], pos[310][310];
    int n, m, ans = 0x3f3f3f3f;
    vector<int> path; //具体方案
    void get_path(int x, int y) {
    	if (pos[x][y] == 0) return;
    	get_path(x, pos[x][y]);
    	path.push_back(pos[x][y]);
    	get_path(pos[x][y], y);
    }
    int main() {
    	cin >> n >> m;
    	memset(a, 0x3f, sizeof(a));
    	for (int i = 1; i <= n; i++) a[i][i] = 0;
    	for (int i = 1; i <= m; i++) {
    		int x, y, z;
    		scanf("%d%d%d", &x, &y, &z);
    		a[y][x] = a[x][y] = min(a[x][y], z);
    	}
    	memcpy(d, a, sizeof(a));
    	for (int k = 1; k <= n; k++) {
    		for (int i = 1; i < k; i++)
    			for (int j = i + 1; j < k; j++)
    				if ((long long)d[i][j] + a[j][k] + a[k][i] < ans) {
    					ans = d[i][j] + a[j][k] + a[k][i];
    					path.clear();
    					path.push_back(i);
    					get_path(i, j);
    					path.push_back(j);
    					path.push_back(k);
    				}
    		for (int i = 1; i <= n; i++)
    			for (int j = 1; j <= n; j++)
    				if (d[i][j] > d[i][k] + d[k][j]) {
    					d[i][j] = d[i][k] + d[k][j];
    					pos[i][j] = k;
    				}
    	}
    	if (ans == 0x3f3f3f3f) {
    		puts("No solution.");
    		return 0;
    	}
    	for (int i = 0; i < path.size(); i++)
    		printf("%d ", path[i]);
    	puts("");
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，249人围观）

还没有评论，来说两句吧...

相关阅读

相关判断图有无环_【转】判断一个图是否有环无向图有向图

无向图：法1：如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。 n算法：第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它

Myth丶恋晨/ 2023年01月10日 05:13/ 0 赞/ 154 阅读

相关 DAG（有向无环图）易懂介绍

DAG看他的结构挺唬人的，但是原理还是蛮简单的。DAG改变的是传统区块链的数据结构。首先简单介绍一下什么是图。一个图（graph）是由两部分组成：点（vertex）和边（edg

谁践踏了优雅/ 2022年09月16日 06:00/ 0 赞/ 250 阅读

相关有向无环图（DAG）的温故知新

当我们学习数据结构的时候，总是觉得很枯燥，而当我们解决实际问题的时候，又往往因为对数据结构了解的匮乏而束手无策。从问题中来，到问题中去，在某一点上的深入思考并且不断的实践积累，

淡淡的烟草味﹌/ 2022年08月29日 10:11/ 0 赞/ 270 阅读

相关 poj 2135 Farm Tour 【无向图最小费用最大流】

题目：[poj 2135 Farm Tour ][poj 2135 Farm Tour] 题意：给出一个无向图，问从 1 点到 n 点然后又回到一点总共的最短路。

约定不等于承诺〃/ 2022年08月13日 18:35/ 0 赞/ 193 阅读

相关【杭电oj1599】find the mincost route无向图最小环

find the mincost route Time Limit: 1000/2000 MS (Java/Others) Memory Limit: 32768/327

￡神魔★判官ぃ/ 2022年07月17日 01:09/ 0 赞/ 122 阅读

相关无向图最小生成树

N个点M条边的无向连通图，每条边有一个权值，求该图的最小生成树。 Input 第1行：2个数N,M中间用空格分隔，N为点的数量，M为边的数量。（2 <= N <= 1000

爱被打了一巴掌/ 2022年06月12日 06:42/ 0 赞/ 170 阅读

相关有向无环图VS树

有向无环图VS树： -------------------- 前言: Big-man在看着 [《终极算法》][Link 1] 的时候，突然一个很要好的朋友（

迈不过友情╰/ 2022年06月08日 09:08/ 0 赞/ 304 阅读

相关 DAG有向无环图

参考 https://ctolib.com/yueyunyue-liteflow.html DAG有向无环图：https://blog.csdn.net/ya

淡淡的烟草味﹌/ 2022年01月26日 06:05/ 0 赞/ 295 阅读

相关加权无向图 - 最小生成树

1. 最小生成树的定义生成树指的是含有所有顶点的无环连通子图。注意这其中的三个限定条件： 1）包含了所有的顶点 2）不存在环 3）连通图 ![1593787-2

古城微笑少年丶/ 2021年12月20日 06:41/ 0 赞/ 267 阅读

相关 poj 1734(无向图的最小环）

题意：n个点，m条边的加权无向图，求其中的最小环，并输出路径。分析：考察对Floyd的理解，详见《算法竞赛进阶指南》P361-362，书中也提到了有向图最小环的解法。

约定不等于承诺〃/ 2021年11月16日 08:31/ 0 赞/ 250 阅读