题目链接：https://vjudge.net/problem/hdu-4514
题意：判断没有没有环，如果没有环，通俗的讲就是找出一条最长的路，相当于一笔画能画多长。
思路：dfs判环。
最后就是没有环的情况了：最长的路的话，我们可以先从一个点a开始遍历所有边，找出最长的路，
但是，那个最长路不一定是一个图的最长路，只能说，从这个点a开始跑，跑到了b是a能跑出的最长路，
那么我们只需要再从b点跑一遍图，因为是一笔画，可能b跑到了c比a跑到b长。
那么b跑出的最长路就是从所有起点开始跑图的图的最长路了。
这个图可能是有很多不联通的子图组成，这个需要注意。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <map> 7 #include <cmath> 8 #include <iomanip> 9 using namespace std; 10 11 typedef long long ll; 12 #define inf (1ll << 25) 13 #define rep(i,j,k) for(int i = (j); i <= (k); i++) 14 #define rep__(i,j,k) for(int i = (j); i < (k); i++) 15 #define per(i,j,k) for(int i = (j); i >= (k); i--) 16 #define per__(i,j,k) for(int i = (j); i > (k); i--) 17 18 const int n = 100010; 19 const int m = 1000010; 20 21 struct node{ 22 23 int to; 24 int w; 25 int next; 26 }edge[m << 1]; 27 28 int head[n]; 29 int cnt;//链式前向星 30 bool vis[n]; 31 bool used[n]; //用于判断子图情况 32 int dis[n]; 33 int n,m; 34 35 void add(int u,int v,int w){ 36 37 edge[cnt].to = v; 38 edge[cnt].w = w; 39 edge[cnt].next = head[u]; 40 head[u] = cnt++; 41 } 42 43 44 bool dfs(int pre,int now){ 45 46 if(used[now]) return true; 47 else { 48 used[now] = true; 49 50 for(int o = head[now]; ~o; o = edge[o].next){ 51 int v = edge[o].to; 52 if(v == pre) continue;//与之前的点不冲突 53 if(dfs(now,v)) return true; 54 } 55 56 return false; 57 } 58 } 59 60 61 void dfs_d(int now){ 62 63 vis[now] = true; 64 used[now] = true; 65 for(int o = head[now]; ~o; o = edge[o].next){ 66 int v = edge[o].to; 67 int w = edge[o].w; 68 if(vis[v]) continue; 69 70 dis[v] = dis[now] + w; 71 dfs_d(v); 72 } 73 } 74 75 int work(int now){ 76 77 rep(i,1,n) dis[i] = 0; 78 rep(i,1,n) vis[i] = false; 79 dfs_d(now); //正跑 80 81 int index = -1; 82 int len = -1; 83 //找到最长的路 84 rep(i,1,n){ 85 if(len < dis[i]) len = dis[i],index = i; 86 } 87 88 rep(i,1,n) dis[i] = 0; 89 rep(i,1,n) vis[i] = false; 90 dfs_d(index);//反跑 91 92 rep(i,1,n) len = max(len, dis[i]); 93 94 return len; 95 } 96 97 int main(){ 98 99 ios::sync_with_stdio(false); 100 cin.tie(0); 101 102 int u,v,w; 103 while(cin >> n >> m){ 104 105 cnt = 0; //边数初始化 106 rep(i,1,n) head[i] = -1; //头初始化 107 108 rep(i,1,m){ 109 cin >> u >> v >> w; 110 111 add(u,v,w); 112 add(v,u,w); 113 } 114 115 rep(i,1,n) used[i] = false; //连通图初始化 116 bool ok = true; 117 118 //head[x] == -1 说明没有边和它相连，那不需要进入函数 119 rep(i,1,n){ 120 if(used[i] || head[i] == -1) continue; 121 122 123 //判断有没有环 124 if(dfs(0,i)){ 125 ok = false; 126 break; 127 } 128 } 129 130 if(!ok) cout << "yes" << endl; 131 else{ 132 133 int ans = -1; 134 rep(i,1,n) used[i] = false; //连通图初始化 135 rep(i,1,n) if(!used[i]) if(head[i] != -1) ans = max(ans, work(i)); 136 137 cout << ans << endl; 138 } 139 } 140 141 getchar(); getchar(); 142 return 0; 143 }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/602437.html