洛谷P6175 无向图的最小环问题

本文主要是介绍洛谷P6175 无向图的最小环问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门：

https://www.luogu.com.cn/problem/P6175

floyd以外无脑暴搜取得伟大胜利（部分得益于数据小

注释小能手又双上线了（天下苦题解不说数组是干什么用的久矣

 1 #include<bits/stdc++.h>
 2 #define ff(i,s,e) for(int i=s;i<=e;i++)
 3 #define fff(i,s,e) for(int i=s;i>=e;i--)
 4 using namespace std;
 5 inline int read(){
 6     register int x=0,f=1;
 7     register char ch=getchar();
 8     while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
 9     while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
10     return x*f;
11 }
12 const int M=1e3*5+2;
13 int n,m,ans=2147383647;
14 int deg[M],d[M][M],nxt[M][M];//第i个点连接的点的数量 第i和第j个点之间边长 存储第i个点下一个可以连接的点们 
15 bool vis[M][M];//搜索用，避免重复 
16 void dfs(int st,int x,int len,int tot){//环起始点，当前点，当前环总长，当前环上点数 
17     if(len>ans) return;//剪大枝 
18     ff(i,1,deg[x]){//遍历与x相连的所有点 
19         if(nxt[x][i]==st&&tot>=3){//可以成环且环上点数大于等于三，更新答案 
20             ans=min(ans,len+d[x][nxt[x][i]]);
21             return;
22         }
23         if(!vis[x][nxt[x][i]]){
24             vis[x][nxt[x][i]]=vis[nxt[x][i]][x]=1;//注意双向标记 
25             dfs(st,nxt[x][i],len+d[x][nxt[x][i]],tot+1);
26             vis[x][nxt[x][i]]=vis[nxt[x][i]][x]=0;//回溯 
27         }
28     }
29 }
30 int main(){
31     n=read();m=read();
32     int u,v,dd;
33     ff(i,1,m){
34         u=read();v=read();dd=read();
35         if(d[u][v]==0) d[u][v]=d[v][u]=dd,nxt[u][++deg[u]]=v,nxt[v][++deg[v]]=u;
36         else d[u][v]=d[v][u]=min(d[u][v],dd);
37         //有判断是因为看到样例两点之间多个长度，直接取最小 
38     }
39     ff(i,1,n){//枚举每个点作为起点 
40         if(deg[i]){//若有点与其相连，搜 
41             dfs(i,i,0,1);
42         }
43     }
44     if(ans!=2147383647) printf("%d",ans);
45     else printf("No solution.");
46     return 0;
47 }

这篇关于洛谷P6175 无向图的最小环问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！