首页 > 代码库 > hdu 4514 湫湫系列故事――设计风景线（求树的直径）
hdu 4514 湫湫系列故事――设计风景线（求树的直径）
随着杭州西湖的知名度的进一步提升，园林规划专家湫湫希望设计出一条新的经典观光线路，根据老板马小腾的指示，新的风景线最好能建成环形，如果没有条件建成环形，那就建的越长越好。
现在已经勘探确定了n个位置可以用来建设，在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线？如果不能，风景线最长能够达到多少？
其中，可以兴建的路线均是双向的，他们之间的长度均大于0。
现在已经勘探确定了n个位置可以用来建设，在它们之间也勘探确定了m条可以设计的路线以及他们的长度。请问是否能够建成环形的风景线？如果不能，风景线最长能够达到多少？
其中，可以兴建的路线均是双向的，他们之间的长度均大于0。
Input 测试数据有多组，每组测试数据的第一行有两个数字n, m，其含义参见题目描述；
接下去m行，每行3个数字u v w，分别代表这条线路的起点，终点和长度。
TechnicalSpecificationTechnicalSpecification
1. n<=100000
2. m <= 1000000
3. 1<= u, v <= n
4. w <= 1000
Output 对于每组测试数据，如果能够建成环形（并不需要连接上去全部的风景点），那么输出YES，否则输出最长的长度，每组数据输出一行。
Sample Input
3 31 2 12 3 13 1 1
Sample Output
YES
求树的直径，用再次bfs。证明见：树的直径（最长路） 的详细证明（转）
首先先判环，如果有环直接输出YES，用并查集就好。如果没有环，那么就是一棵树，然后最长的就是树的直径，这个题注意少开内存，容易超内存，
还有用C++交用的少一些，我用G++交的卡在32764K，限制是32768K。。
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include <cstdio> 3 #include <string> 4 #include <cstdlib> 5 #include <cmath> 6 #include <iostream> 7 #include <cstring> 8 #include <set> 9 #include <queue> 10 #include <algorithm> 11 #include <vector> 12 #include <map> 13 #include <cctype> 14 #include <cmath> 15 #include <stack> 16 //#include <tr1/unordered_map> 17 #define freopenr freopen("in.txt", "r", stdin) 18 #define freopenw freopen("out.txt", "w", stdout) 19 using namespace std; 20 //using namespace std :: tr1; 21 22 typedef long long LL; 23 typedef pair<int, int> P; 24 const int INF = 0x3f3f3f3f; 25 const double inf = 0x3f3f3f3f3f3f; 26 const LL LNF = 0x3f3f3f3f3f3f; 27 const double PI = acos(-1.0); 28 const double eps = 1e-8; 29 const int maxn = 1e5 + 5; 30 const LL mod = 10000000000007; 31 const int N = 1e6 + 5; 32 const int dr[] = {-1, 0, 1, 0, 1, 1, -1, -1}; 33 const int dc[] = {0, 1, 0, -1, 1, -1, 1, -1}; 34 const char *Hex[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"}; 35 inline LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a%b); } 36 int n, m; 37 const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 38 const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 39 inline int Min(int a, int b){ return a < b ? a : b; } 40 inline int Max(int a, int b){ return a > b ? a : b; } 41 inline LL Min(LL a, LL b){ return a < b ? a : b; } 42 inline LL Max(LL a, LL b){ return a > b ? a : b; } 43 inline bool is_in(int r, int c){ 44 return r >= 0 && r < n && c >= 0 && c < m; 45 } 46 vector<P> G[maxn]; 47 int p[maxn], dp[maxn]; 48 bool vis[maxn], viss[maxn]; 49 50 int Find(int x){ return x == p[x] ? x : p[x] = Find(p[x]); } 51 52 int bfs(int root){ 53 memset(vis, false, sizeof vis); 54 memset(dp, 0, sizeof dp); 55 queue<int> q; 56 q.push(root); 57 vis[root] = viss[root] = true; 58 int ans = root, maxx = 0; 59 60 while(!q.empty()){ 61 int u = q.front(); q.pop(); 62 for(int i = 0; i < G[u].size(); ++i){ 63 P p = G[u][i]; 64 int v = p.first; 65 int w = p.second; 66 if(vis[v]) continue; 67 vis[v] = viss[v] = true; 68 dp[v] = dp[u] + w; 69 if(maxx < dp[v]){ 70 maxx = dp[v]; 71 ans = v; 72 } 73 q.push(v); 74 } 75 } 76 return ans; 77 } 78 79 int solve(int root){ 80 int u = bfs(root); 81 int v = bfs(u); 82 return dp[v]; 83 } 84 85 int main(){ 86 while(scanf("%d %d", &n, &m) == 2){ 87 int u, v, c; 88 for(int i = 1; i <= n; ++i) G[i].clear(), p[i] = i; 89 bool ok = false; 90 for(int i = 0; i < m; ++i){ 91 scanf("%d %d %d", &u, &v, &c); 92 int x = Find(u); 93 int y = Find(v); 94 if(x != y) p[y] = x; 95 else ok = true; 96 G[u].push_back(P(v, c)); 97 G[v].push_back(P(u, c)); 98 } 99 if(ok){ puts("YES"); continue; }100 101 memset(viss, false, sizeof viss);102 int ans = 0;103 for(int i = 1; i <= n; ++i)104 if(!viss[i]) ans = Max(ans , solve(i));105 printf("%d\n", ans);106 }107 return 0;108 }
如果没想到上面的方法，用dp也是可以做的。
树的直径是其子树直径的最大值，也是叶子节点中的距离的最大值。
dp[i]表示子树i 的高度
枚举所有的节点u，找出以u为中间节点的距离的最大值。
1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<string> 6 #include<cmath> 7 #include<cstdlib> 8 #include<algorithm> 9 #include<vector>10 using namespace std;11 struct node12 {13 int v,w;14 node(int _v, int _w) : v(_v), w(_w) {}15 };16 vector<node> e[100001];17 int n,m,fa[100001],dp[100001],ans;18 int find(int x)19 {20 if(x!=fa[x])21 fa[x]=find(fa[x]);22 return fa[x];23 }24 void dfs(int u,int father)25 {26 int maxx=0;27 for(int i=0;i<e[u].size();i++)28 {29 int v=e[u][i].v;30 int w=e[u][i].w;31 if(v==father)32 continue;33 dfs(v,u);34 ans=max(ans,dp[v]+maxx+w);35 maxx=max(maxx,dp[v]+w);36 }37 dp[u]=maxx;38 }39 void slove()40 {41 for(int i=1;i<=n;i++)42 {43 if(dp[i]==-1)44 dfs(i,-1);45 }46 printf("%d\n",ans);47 }48 int main()49 {50 while(scanf("%d%d",&n,&m)!=EOF)51 {52 bool flag=false;53 ans=0;54 for(int i=1;i<=n;i++)55 fa[i]=i,dp[i]=-1,e[i].clear();56 for(int i=1;i<=m;i++)57 {58 int x,y,z;59 scanf("%d%d%d",&x,&y,&z);60 e[x].push_back(node(y,z));61 e[y].push_back(node(x,z));62 if(flag)63 continue;64 int fx,fy;65 fx=find(x),fy=find(y);66 if(fx!=fy)67 {68 fa[fx]=fy;69 }70 else71 {72 flag=true;73 continue;74 }75 }76 if(flag)77 {78 printf("YES\n");79 continue;80 }81 slove();82 }83 return 0;84 }
hdu 4514 湫湫系列故事――设计风景线（求树的直径）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。