BZOJ 1487: [HNOI2009] 무귀도
매번 링에 DP가 있을 때마다 링의 뿌리(즉 링에서 첫 번째로 발견된 노드) 왼쪽의 노드를 취하거나 취하지 않도록 강제한다.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=100000+5;
const int inf=1e9;
struct Edge{int to,next;}e[N<<2];
int head[N],cnt;
void ins(int u,int v){
e[++cnt]=(Edge){v,head[u]};head[u]=cnt;
}
int power[N],f[N],g[N],pre[N];
void dp(int rt,int x){
int ans0=0,ans1=0,now0,now1;
for(int i=x;i!=rt;i=pre[i]){
now0=ans0+g[i];now1=ans1+f[i];
ans0=max(now0,now1);ans1=now0;
}
g[rt]+=ans0;
ans0=0;ans1=-inf;
for(int i=x;i!=rt;i=pre[i]){
now0=ans0+g[i];now1=ans1+f[i];
ans0=max(now0,now1);ans1=now0;
}
f[rt]+=ans1;
}
int dfn[N],dfs_clock;
void dfs(int u){
dfn[u]=++dfs_clock;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(!dfn[v])pre[v]=u,dfs(v);
}
f[u]=power[u];
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(dfn[v]>dfn[u]&&pre[v]!=u)
dp(u,v);
}
}
int main(){
//freopen("a.in","r",stdin);
int n,m;scanf("%d%d",&n,&m);
while(m--){
int u,v;scanf("%d%d",&u,&v);
ins(u,v);ins(v,u);
}
for(int i=1;i<=n;i++)scanf("%d",&power[i]);
dfs(1);
printf("%d
",max(f[1],g[1]));
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.