题意:给定一棵树,然后让你找出它的直径,也就是两点中的最远距离。

析:很明显这是一个树上DP,应该有三种方式,分别是两次DFS,两次BFS,和一次DFS,我只写了后两种。

代码如下:

两次BFS:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue> using namespace std;
const int maxn = 1e5 + 5;
int d[maxn];
bool vis[maxn], vvis[maxn];//vis是BFS的标记,vvis是总的标记
vector<int> G[maxn], w[maxn];
//思路就是先在树上找一个点,然后从这个点开始找,找最远的点,
//然后两从最远的点找最远的点,这个所有点中的最大值就是树的直径
//d[i]表示到结点 i 的最长距离
int bfs(int root){
memset(vis, false, sizeof(vis));
memset(d, 0, sizeof(d));
queue<int> q;
q.push(root);
int ans = root, m = 0;
vis[root] = vvis[root] = true;
while(!q.empty()){
root = q.front(); q.pop();
for(int i = 0; i < G[root].size(); ++i){
int u = G[root][i];
if(vis[u]) continue;
q.push(u);
vis[u] = vvis[u] = true;
d[u] = d[root] + w[root][i];
if(d[u] > m){
ans = u;
m = d[u];
}
}
}
return ans;
} void init(int n){
for(int i = 1; i <= n; ++i){
G[i].clear();
w[i].clear();
vvis[i] = false;
}
} int main(){
int n, m, u, v, l;
char ch;
while(cin >> n >> m){
init(n);
while(m--){
scanf("%d %d %d %c", &u, &v, &l, &ch);
G[u].push_back(v); w[u].push_back(l);
G[v].push_back(u); w[v].push_back(l);
} int ans = 0;
for(int i = 1; i <= n; ++i)
if(!vvis[i]) ans = max(ans, d[bfs(bfs(i))]);//两次BFS,第一次是找最远的点,第二次是找最远点的最远点
cout << ans << endl;
}
return 0;
}

一次DFS:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue> using namespace std;
const int maxn = 1e5 + 5;
int f[maxn], g[maxn], ll[maxn];
vector<int> G[maxn], w[maxn];
//思路主要是找一个点的最远点加次远点就是树的直径 int dfs(int root, int fa){
if(f[root] != -1) return f[root];
if(!G[root].size()) return f[root] = 0;
int m = 0, ans = root;
for(int i = 0; i < G[root].size(); ++i){
int u = G[root][i];
if(u == fa) continue;
if(dfs(u, root) + w[root][i] > m){
m = f[u] + w[root][i];
ans = u;
}
} ll[root] = ans; int mm = 0;
for(int i = 0; i < G[root].size(); ++i){
int u = G[root][i];
if(u == fa) continue;
if(f[u] + w[root][i] > mm && u != ll[root])
mm = f[u] + w[root][i];
}
g[root] = mm;
return f[root] = m;
} void init(int n){
for(int i = 1; i <= n; ++i){
G[i].clear();
w[i].clear();
f[i] = g[i] = ll[i] = -1;
}
} int main(){
int n, m, u, v, l;
char ch;
while(cin >> n >> m){
init(n);
while(m--){
scanf("%d %d %d %c", &u, &v, &l, &ch);
G[u].push_back(v); w[u].push_back(l);
G[v].push_back(u); w[v].push_back(l);
} int ans = 0;
for(int i = 1; i <= n; ++i)
if(f[i] == -1) dfs(i, -1);
for(int i = 1; i <= n; ++i) ans = max(ans, f[i]+g[i]);
cout << ans << endl;
}
return 0;
}
05-11 22:35