我太水了 发现树的直径好像没有弄透彻 然后就重新清理了一遍 把树形dp的做法和两遍dfs的做法重新清理了一遍
树形dp求树的直径
核心:
//f[x]是以x为节点的子树的直径 int f[N];bool vis[N]; void dp(int u) { vis[u]=1; for(rg int i=head[u];i;i=e[i].nxt) { int v=e[i].v,w=e[i].w; if(vis[v]) continue; dp(v); ans=max(ans,f[u]+f[v]+w); f[u]=max(f[u],f[v]+w); } }
#include<bits/stdc++.h> using namespace std; const int N=1005; const int inf=0x3f3f3f; int n,f[N][2],ans=0; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } int head[N],tot=0; struct edge{int v,w,nxt;}e[N<<1]; void add(int u,int v,int w){ e[++tot]=(edge){v,w,head[u]},head[u]=tot; } void dp(int u,int fa){ f[u][1]=0,f[u][2]=0; for(int i=head[u],v,w;i;i=e[i].nxt){ w=e[i].w,v=e[i].v; if(v==fa) continue; dp(v,u);//搜儿子 int dis=f[v][1]+w; if(dis>f[u][1]) f[u][2]=f[u][1],f[u][1]=dis; else if(dis>f[u][2]) f[u][2]=dis; ans=max(ans,f[u][1]+f[u][2]); } } int main(){ memset(head,0,sizeof(head)); rd(n); for(int i=1,u,v,w;i<n;++i) rd(u),rd(v),rd(w),add(u,v,w),add(v,u,w); dp(1,0); printf("%d",ans); return 0; }
两遍dfs求树的直径
核心:
void dfs(int u,int fa) { if(f[u]>=maxl) s=u,maxl=f[u]; for(rg int i=head[u];i;i=e[i].nxt) { int v=e[i].v,w=e[i].w; if(v==fa) continue; f[v]=f[u]+w; dfs(v,u); } }
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define ll long long #define rg register const int N=10000+5,P=9901,inf=0x3f3f3f3f; int s,sf,maxl; template <class t>void rd(t &x){ x=0;int w=0;char ch=0; while(!isdigit(ch)) w|=ch=='-',ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=w?-x:x; } int head[N],tot=0; struct edge{int v,w,nxt;}e[N<<1]; void add(int u,int v,int w){ e[++tot]=(edge){v,w,head[u]},head[u]=tot; } int f[N]; void dfs(int u,int fa){ if(f[u]>=maxl) s=u,maxl=f[u]; for(rg int i=head[u],v,w;i;i=e[i].nxt){ v=e[i].v,w=e[i].w; if(v==fa) continue; f[v]=f[u]+w; dfs(v,u); } } int main(){ // freopen("in.txt","r",stdin); //freopen("nocows.out","w",stdout); int u,v,w; memset(f,0,sizeof(f)); while(scanf("%d%d%d",&u,&v,&w)==3) add(u,v,w),add(v,u,w); dfs(1,0);maxl=-1; memset(f,0,sizeof(f));dfs(s,0); printf("%d",maxl); return 0; }