BZOJ 2809 [Apio 2012] dispatching 병합 가능
제목:링크
방법: 병합 가능
해결:
물 문제, 그러나 주의 과정 폭발 int.
방법은 나무의 뿌리 노드를 찾아서 쓸고 모든 자수 따위를 하나의 무더기로 간주한 다음에 합치는 것이다. 무더기 중의sum와 m를 초과하면 가장 큰 것을 빼고 계속 첨가하는 것이 분명하다.
그리고 매번 점 하나를 처리하고 무더기로 답안을 갱신한다.
앞의 두 물보다
코드:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 100100
using namespace std;
typedef long long ll;
int n,m,all_root,cnt;
ll ans;
int head[N],h[N],fa[N],ch[N][2],root[N];
ll sum[N],val[N],lead[N],size[N];
struct node
{
int from,to,next;
}edge[N];
int find(int x){return fa[x]==x?fa[x]:fa[x]=find(fa[x]);}
void pushup(int x){sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];size[x]=size[ch[x][0]]+size[ch[x][1]]+1;}
void init()
{
memset(head,-1,sizeof(head)),cnt=1;
for(int i=1;i<=n;i++)fa[i]=i;
}
void edgeadd(int from,int to)
{
edge[cnt].to=to,edge[cnt].next=head[from],head[from]=cnt++;
}
int merge(int x,int y)
{
if(!x)return y;
if(!y)return x;
if(val[x]<val[y])swap(x,y);
ch[x][1]=merge(ch[x][1],y);
if(h[ch[x][1]]>h[ch[x][0]])swap(ch[x][1],ch[x][0]);
h[x]=h[ch[x][1]]+1;
return x;
}
void dfs(int x)
{
sum[x]=val[x],size[x]=1;
for(int i=head[x];i!=-1;i=edge[i].next)
{
int to=edge[i].to;
dfs(to);
sum[x]+=sum[to];size[x]+=size[to];
fa[x]=merge(fa[x],fa[to]);
}
while(sum[x]>m)
{
sum[x]-=val[fa[x]],size[x]--;
fa[x]=merge(ch[fa[x]][0],ch[fa[x]][1]);
}
ans=max(lead[x]*size[x],ans);
}
int main()
{
h[0]=-1;
scanf("%d%d",&n,&m);
init();
for(int i=1;i<=n;i++)
{
int f,v,l;
scanf("%d%d%d",&f,&v,&l);
if(!f){all_root=i,val[i]=v,lead[i]=l,size[i]=1;continue;}
edgeadd(f,i);
val[i]=v,lead[i]=l,size[i]=1;
}
dfs(all_root);
printf("%lld
",ans);
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
vue 단일 페이지에 여러 개의 echarts 도표가 있을 때의 공용 코드 쓰기html에서: 데이터 처리는 말할 필요가 없다.응, 직접 그림을 그려: 공통 섹션: 이 페이지를 떠날 때 파괴: 추가 정보: Vue + Echarts 차트 표시 및 동적 렌더링 준비 작업 echarts 의존 설치 n...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.