Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 求出最长与次长距离，然后相加求最大值，又wa了，。求解

Posted by celia01 at 2012-07-27 20:14:02 on Problem 1985
```这道题用了3中思路写，一种wa，一种tle，只用用bfs写的过了，而且用bfs写的测试了一下数据，发现数据应该始终是在包含节点1的树中得到的～～，很难以理解前两种做法的wa

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 40005;
int f[maxn], g[maxn], longest[maxn];
vector<int> son[maxn], w[maxn];
bool vis[maxn];
int dfs(int root){
int i, j;
int est = 0, esti=-1, er=0;
if(f[root]!=-1) return f[root];
if(son[root].empty()) return f[root] = 0;
for(i=0;i<son[root].size();i++){
if(dfs(son[root][i])+w[root][i]>est){
est = f[son[root][i]]+w[root][i];
esti = i;
}
}
longest[root] = esti;
for(i=0;i<son[root].size();i++){
if(f[son[root][i]]+w[root][i]>er&&i!=longest[root]){
er = f[son[root][i]]+w[root][i];
}
}
g[root] = er;
return f[root] = est;
}

void Init(int n){
int i;
for(i=0;i<=n;i++){
f[i] = g[i] = longest[i] = -1;
son[i].clear();
w[i].clear();
vis[i] = 0;
}
}
int main(){
int i, j, k, n, m, ans;
int x1, x2, l;
char opt;
while(~scanf("%d%d",&n,&m)){
Init(n);
for(i=0;i<m;i++){
scanf("%d%d%d",&x1,&x2,&l);
scanf(" %c",&opt);
if(opt=='E'||opt=='S'){
son[x1].push_back(x2);
w[x1].push_back(l);
vis[x2] = 1;
}
else{
son[x2].push_back(x1);
w[x2].push_back(l);
vis[x1] = 1;
}
}
for(i=1;i<=n;i++){
if(vis[i]==0&&f[i]==-1){
f[i] = dfs(i);
}
}
ans = 0;
for(i=1;i<=n;i++){
ans = max(ans,f[i]+g[i]);
}
printf("%d\n",ans);
}
return 0;
}
```

Followed by: