poj 2631 Roads in the North BFS树状DP

传送门:poj 2631 Roads in the North

题目大意

输入边的两个顶点和权值，输出任意两个顶点的最远距离；

解题思路

这是一个裸的求树的直径的题目。 先说用BFS的方式，第一个BFS随便找一个顶点进行松弛，找到最远的一条路径并且记录下来那个顶点，因为这个距离肯定是包含在了最后的最长路径里面，所以在对刚才找到的那个节点进行一次BFS找到就是树的直径。

AC代码

#include<cstdio> #include<cstring> #include<queue> using namespace std; const int MAXN = 10000 + 5000; const int INF = 0x3f3f3f3f; int head[MAXN],e; long long dis[MAXN],ans; bool vis[MAXN]; struct Edge{ int v,nxt,w; }E[MAXN<<1]; void init() { e=0; memset(head,-1,sizeof head); } void add(int u,int v,int w) { E[e].v=v; E[e].w=w; E[e].nxt = head[u]; head[u]=e++; } int BFS(int s) { int se = s; long long MAX = 0; ans = 0; queue<int>Q; Q.push(s); memset(vis,false,sizeof vis); vis[s] = true; dis[s] = 0; while(!Q.empty()) { int u = Q.front();Q.pop(); for(int i=head[u];~i;i=E[i].nxt){ int v = E[i].v; if(vis[v])continue; vis[v] = true; dis[v] = dis[u]+E[i].w; if(dis[v]>MAX){ se = v; MAX = dis[v]; ans = dis[v]; } Q.push(v); } } return se; } int main() { int u,v,w; // freopen("in.txt","r",stdin); init(); while(scanf("%d%d%d",&u,&v,&w) != EOF){ add(u,v,w); add(v,u,w); } BFS(BFS(1)); printf("%lld\n",ans); return 0; }

还有一种方法就是使用树状DP。 dis[i][0]表示第i个节点的子树中最长的距离； dis[i][1]表示第i个节点的子树中次长的距离； 如下图： 首先先要递归到叶子节点，比如说先递归到了I节点: dp[I][0] = 7; dp[I][1] = 0; 然后递归到了D节点 dp[D][0] = 13; dp[D][1] = 1; 最后一直到A节点，他的子树的最大长度和子树的次大长度就是树的直径！ 然后就是维护每个节点子树的最长距离和次长距离就可以了！

AC代码

#include<cstdio> #include<cstring> const int MAXN = 1e5+50; int head[MAXN],e,dis[MAXN][3]; bool vis[MAXN]; struct Edge{ int u,v,nxt,w; }E[MAXN<<1]; void add(int u,int v,int w) { E[e].v = v; E[e].w = w; E[e].nxt=head[u]; head[u] = e++; } void DFS(int u) { vis[u] = true; //printf("[%d]\n",u); for(int i=head[u];~i;i=E[i].nxt){ int v = E[i].v; if(vis[v])continue; DFS(v); if(dis[u][0]<dis[v][0]+E[i].w){ dis[u][1] = dis[u][0]; dis[u][0] = dis[v][0]+E[i].w; } else if(dis[u][1]<dis[v][0]+E[i].w) dis[u][1] = dis[v][0]+E[i].w; } } int main() { e=0;memset(vis,false,sizeof vis); memset(head,-1,sizeof head); memset(dis,0,sizeof dis); int u,v,w,n=0,ans=0; //freopen("in.txt","r",stdin); while(~scanf("%d%d%d",&u,&v,&w)){ add(u,v,w);add(v,u,w); n++; } DFS(1); for(int i=1;i<=n;i++) if(ans<dis[i][0]+dis[i][1]) ans = dis[i][0] + dis[i][1]; printf("%d\n",ans); return 0; }