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

## 最开始求出了每个点与自己最远距离的差，用的是O(n)的算法求解的，然后在求最大值，为何Tle了

Posted by celia01 at 2012-07-27 17:39:17 on Problem 1985 and last updated at 2012-07-27 17:39:36
```        for(i=1;i<=n;i++){
if(f[i]==-1){
f[i] = dfs(i);
h[i] = 0; dfs1(i);
}
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 40005;
int f[maxn], g[maxn], h[maxn], longest[maxn];
vector<int> son[maxn], w[maxn];

int dfs(int root){
int i, j;
int est = 0, esti, 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 dfs1(int root){
int i, j;
for(i=0;i<son[root].size();i++){
if(i!=longest[root]){
h[son[root][i]] = max(f[root],h[root])+w[root][i];
}
else{
h[son[root][i]] = max(g[root],h[root])+w[root][i];
}
dfs1(son[root][i]);
}
}

void Init(int n){
int i;
for(i=0;i<=n;i++){
f[i] = g[i] = h[i] = longest[i] = -1;
son[i].clear();
w[i].clear();
}
}
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);
}
else{
son[x2].push_back(x1);
w[x2].push_back(l);
}
}
for(i=1;i<=n;i++){
if(f[i]==-1){
f[i] = dfs(i);
h[i] = 0; dfs1(i);
}
}
ans = 0;
for(i=1;i<=n;i++){
ans = max(ans,max(f[i],h[i]));
}
printf("%d\n",ans);
}
return 0;
}
```

Followed by: