2021.11.03 P6175 无向图的最小环问题

P6175 无向图的最小环问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：

给定一张无向图，求图中一个至少包含 33 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。在本题中，你需要输出最小的环的边权和。若无解，输出 No solution.

分析：

对于floyed，在第k个点时，任意的i到j之间的最短路已经经过了(k-1)个点。

代码如下：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

#define int long long

const int N=110;

int n,m,dis[N][N],a[N][N],ans=2e9;

inline int read(){

	int s=0,w=1;

	char ch=getchar();

	while(ch<'0'||ch>'9'){

		if(ch=='-')w=-1;

		ch=getchar();

	}

	while(ch<='9'&&ch>='0'){

		s=s*10+ch-'0';

		ch=getchar();

	}

	return s*w;

}

signed main(){

	n=read();m=read();

	//memset(dis,ans,sizeof(dis));

	//memset(a,ans,sizeof(a));

	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=dis[i][j]=1e9;

	for(int i=1;i<=m;i++){

		int u,v,w;

		u=read();v=read();w=read();

		dis[u][v]=dis[v][u]=a[u][v]=a[v][u]=w;

	}

	for(int k=1;k<=n;k++){

		for(int i=1;i<k;i++)

		for(int j=1;j<i;j++)

		ans=min(ans,dis[i][j]+a[i][k]+a[k][j]);

        //重点：i、j如果相重必须初始化为0，如dis[i][i]=0，而且因为只有前k-1个点被完全利用了，即，以其为断点优化过，因为是无向图，所以dis[i][j]==dis[j][i]，枚举一次就够了

		for(int i=1;i<=n;i++)

		for(int j=1;j<=n;j++)

		dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

	}

	if(ans<1e9)cout<<ans;

	else cout<<"No solution.";

	return 0;

}

巴特西

2021.11.03 P6175 无向图的最小环问题

2021.11.03 P6175 无向图的最小环问题

最新文章

热门文章