给定一张图,求图中一个至少包含三个点的环,环上的点不重复,并且环上的边的长度之和最小.
点数不超过100个
输出方案
无向图:
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + ;
const int gakki = + + + + 1e9;
const int MAXN = 3e2 + , MAXM = 2e5 + ;
int a[MAXN][MAXN], d[MAXN][MAXN], pos[MAXN][MAXN];
int n, m;
int ans = 0x3f3f3f3f;
vector<int> path;
void get_path(int x, int y)
{
if (pos[x][y] == )
{
return ;
}
get_path(x, pos[x][y]);
path.push_back(pos[x][y]);
get_path(pos[x][y], y);
}
int main()
{
scanf("%d %d", &n, &m);
mem(a, 0x3f);
for (int i = ; i <= n; i++)
{
a[i][i] = ;
}
for (int i = ; i <= m; i++)
{
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
a[x][y] = a[y][x] = min(a[x][y], z);
}
memcpy(d, a, sizeof(a));
for (int k = ; k <= n; k++)
{
//刚开始循环时 d[i][j]表示经过编号不超过k-1的节点从i到j的最短路
for (int i = ; i < k; i++)
{
for (int j = i + ; j < k; j++)
{
if ((ll)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 = ; i <= n; i++)
{
for (int j = ; 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)
{
printf("No solution.\n");
}
else
{
for (int i = ; i < path.size(); i++)
{
printf("%d ", path[i]);
}
printf("\n");
}
return ;
}
//无向图最小环
有向图:
有向图直接floyd求出最小的自身到自身的距离 即为答案(注意初始化全为INF)