【tyvj1520】 나무의 직경(dfs|||나무형 dp)
하이퍼링크입니다.
문제 풀이:
제목은 dfs의 방법을 주었지만, 마이너스 권한이 있을 때는 사용할 수 없다
또 하나의 dp 방법은 f[i]g[i]가 각각 i에서 그의 서브트리에 점 거리의 최대치와 차대치를 나타낸다. 답은 max(f[i]+g[i])인데 왜 가중되지 않을까?한 변마다 한 번만 훑어볼 수 있기 때문에 체인 모양이면 f[i]의 값만 있고 g[i]의 값은 없다
코드:
dfs:
#include
#define N 50000
using namespace std;
int tot,nxt[N],point[N],v[N],c[N],ans,ansp;
void addline(int x,int y,int cap)
{
++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=cap;
++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=cap;
}
void dfs(int x,int fa,int dis)
{
if (dis>ans) ans=dis,ansp=x;
for (int i=point[x];i;i=nxt[i])
if (v[i]!=fa) dfs(v[i],x,dis+c[i]);
}
void askans(int x,int fa,int dis)
{
if (dis>ans) ans=dis;
for (int i=point[x];i;i=nxt[i])
if (v[i]!=fa) dfs(v[i],x,dis+c[i]);
}
int main()
{
int n,i;
scanf("%d",&n);
for (i=1;i dp:
#include
#include
#define N 50000
using namespace std;
int tot,nxt[N],point[N],v[N],c[N],ans,f[N],g[N],n,i;
void addline(int x,int y,int cc)
{
++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=cc;
++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=cc;
}
void treedp(int x,int fa)
{
for (int i=point[x];i;i=nxt[i])
if (v[i]!=fa)
{
treedp(v[i],x);
if (f[v[i]]+c[i]>f[x])
{
g[x]=f[x];
f[x]=f[v[i]]+c[i];
}
else g[x]=max(g[x],f[v[i]]+c[i]);
}
ans=max(ans,f[x]+g[x]);
}
int main()
{
scanf("%d",&n);
for (i=1;i 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
