随着杭州西湖的知名度的进一步提升，园林规划专家湫湫希望设计出一条新的经典观光线路，根据老板马小腾的指示，新的风景线最好能建成环形，如果没有条件建成环形，那就建的越长越好。 现在已经勘探确定了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 3
1 2 1
2 3 1
3 1 1
Sample Output
YES
求树的直径，用再次bfs。证明见：树的直径（最长路） 的详细证明（转）
首先先判环，如果有环直接输出YES，用并查集就好。如果没有环，那么就是一棵树，然后最长的就是树的直径，这个题注意少开内存，容易超内存，
还有用C++交用的少一些，我用G++交的卡在32764K，限制是32768K。。
1 #pragma comment(linker, "/STACK:1024000000,1024000000")
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 #include
14 #include
15 #include
16 //#include
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
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
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
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 }
View Code
如果没想到上面的方法，用dp也是可以做的。
树的直径是其子树直径的最大值，也是叶子节点中的距离的最大值。
dp[i]表示子树i 的高度
枚举所有的节点u，找出以u为中间节点的距离的最大值。
1 #pragma comment(linker, "/STACK:1024000000,1024000000")
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 using namespace std;
11 struct node
12 {
13 int v,w;
14 node(int _v, int _w) : v(_v), w(_w) {}
15 };
16 vector
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 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 else 71 { 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 } View Code 文章来源
发表评论