首页 > > 程序设计 > C/C++ >

湫湫系列故事——设计风景线 HDU - 4514

2019-08-16 07:59:17来源：博客园阅读 ()

湫湫系列故事——设计风景线 HDU - 4514

题目链接：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 }