HDU 2586 How far away ?(LCA Tarjan / 나무 에 배가)
제목: 두 점 사이 의 가장 짧 은 경 로 를 물 어보 세 요.
타 잔 으로 하면...
LCA 로 최근 공공 조상 lca 를 계산 하면 길이 가 dis [u] + dis [v] - 2 * dis [lca] 입 니 다.
#include
#include
#include
#include
#include
#include
#define eps 1e-8
#define memset(a,v) memset(a,v,sizeof(a))
using namespace std;
typedef long long int LL;
const int MAXL(4*1e4);
const int INF(0x7f7f7f7f);
const int mod(1e9+7);
int dir[4][2]= {{-1,0},{1,0},{0,1},{0,-1}};
struct node
{
int to;
int next,w;
} edge[2*MAXL+50];
int head[2*MAXL+50];
int father[MAXL+50];
int ans[MAXL+50];
int dis[MAXL+50];
bool vis[MAXL+50];
int x[MAXL+50],y[MAXL+50];
struct nodee
{
int ed,id;
} nod;
vectorv[MAXL+50];
int cnt;
int Find(int x)
{
if(x!=father[x])
father[x]=Find(father[x]);
return father[x];
}
void Join(int x,int y)
{
int fx=Find(x),fy=Find(y);
if(fx!=fy)
father[fy]=fx;
}
void LCA(int u)
{
vis[u]=true;
for(int i=head[u]; ~i; i=edge[i].next)
{
int v=edge[i].to,w=edge[i].w;
if(!vis[v])
{
dis[v]=dis[u]+w;
LCA(v);
Join(u,v);
}
}
for(int i=0; i
나무 에 배가 되다
#include
#include
#include
#include
#include
#include
#define eps 1e-8
#define swap(a,b) (a=a+b,b=a-b,a=a-b)
#define memset(a,v) memset(a,v,sizeof(a))
using namespace std;
typedef long long int LL;
const int MAXL(4*1e4);
const int INF(0x7f7f7f7f);
const int mod(1e9+7);
int dir[4][2]= {{-1,0},{1,0},{0,1},{0,-1}};
struct node{
int to,next,w;
node(){}
node(int to,int next,int w):to(to),next(next),w(w){}
}edge[2*MAXL+50];
int head[2*MAXL+50];
int depth[MAXL+50];
int dp[MAXL+50][20];
int dis[MAXL+50][20];
bool vis[MAXL+50];
int n,q,cnt;
void init(){
cnt=0;
memset(head,-1);
memset(dp,0);
memset(depth,0);
memset(dis,0);
memset(vis,false);
}
void add_edge(int x,int y,int z){
edge[cnt]=node(y,head[x],z);
head[x]=cnt++;
}
void getDepth(int u){
vis[u]=true;
for(int i=head[u];~i;i=edge[i].next){
int to=edge[i].to,w=edge[i].w;
if(!vis[to]){
depth[to]=depth[u]+1;
dis[to][0]=w;
dp[to][0]=u;
getDepth(to);
}
}
}
void getDp(){
for(int up=1;(1<=0;j--)
if(depth[x]-(1<=depth[y])
ans+=dis[x][j],x=dp[x][j];
if(x==y) return ans;
for(int j=i;j>=0;j--){
if(dp[x][j]!=dp[y][j]){
ans+=dis[x][j];
ans+=dis[y][j];
x=dp[x][j];
y=dp[y][j];
}
}
return ans+dis[x][0]+dis[y][0];
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
init();
scanf("%d%d",&n,&q);
for(int i=1;i
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.