首页 > 代码库 > bzoj2286: [Sdoi2011]消耗战
bzoj2286: [Sdoi2011]消耗战
思路:建出虚树然后treedp即可,f[i]表示将以i为根的子树与根隔绝的最小代价,f[i]=min(val[i],Σf[son[i]])(val[i]表示将点i与根隔绝的代价),需要注意的是如果i就是关键点那么f[i]=val[i]。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define maxn 250005 #define inf (~0ull>>1) #define min(x,y) (x)>(y)?(y):(x) int n,tot,deg,m,top; int now[maxn],pre[maxn*2],son[maxn*2],val[maxn*2],dfn[maxn],dep[maxn]; int a[maxn],stack[maxn]; long long dp[maxn],minval[maxn]; int f[maxn][21]; bool vis[maxn]; inline int read(){ int x=0;char ch=getchar(); for (;ch<‘0‘||ch>‘9‘;ch=getchar()); for (;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=x*10+ch-‘0‘; return x; } void add(int a,int b,int c){ son[++tot]=b; pre[tot]=now[a]; now[a]=tot; val[tot]=c; } void link(int a,int b,int c){ add(a,b,c),add(b,a,c); } void dfs(int x,int fa){ dep[x]=dep[fa]+1,dfn[x]=++deg; for (int p=now[x];p;p=pre[p]) if (son[p]!=fa){ f[son[p]][0]=x,minval[son[p]]=min(minval[x],val[p]); dfs(son[p],x); } } int lca(int a,int b){ if (dep[a]<dep[b]) swap(a,b);int x=dep[a]-dep[b],t=0; for (;x;x>>=1,t++) if (x&1) a=f[a][t]; if (a==b) return a;t=log2(dep[a])+1; for (;f[a][0]!=f[b][0];){ for (;f[a][t]==f[b][t];) t--; a=f[a][t],b=f[b][t]; } return f[a][0]; } void tree_dp(int x){ dp[x]=minval[x];long long sum=0; for (int p=now[x];p;p=pre[p]) tree_dp(son[p]),sum+=dp[son[p]]; if (sum&&!vis[x]) dp[x]=min(dp[x],sum);now[x]=0; } bool cmp(int a,int b){return dfn[a]<dfn[b];} int main(){ n=read();minval[1]=inf; for (int i=1,aa,b,c;i<n;i++) aa=read(),b=read(),c=read(),link(aa,b,c); dfs(1,0); memset(now,0,sizeof(now)),tot=0; m=read(); for (int i=1;i<=20;i++) for (int x=1;x<=n;x++) f[x][i]=f[f[x][i-1]][i-1]; while (m--){ int len=read();top=0; for (int i=1;i<=len;i++) a[i]=read(),vis[a[i]]=1; sort(a+1,a+len+1,cmp); for (int i=1;i<=len;i++){ if (!top){stack[++top]=a[i];continue;} int x=lca(stack[top],a[i]); for (;dfn[x]<dfn[stack[top]];){ if (dfn[x]>=dfn[stack[top-1]]){ add(x,stack[top],0); if (stack[--top]!=x) stack[++top]=x; break; } add(stack[top-1],stack[top],0),top--; } stack[++top]=a[i]; } while (top>1) add(stack[top-1],stack[top],0),top--; tree_dp(stack[1]),printf("%lld\n",dp[stack[1]]); for (int i=1;i<=len;i++) vis[a[i]]=0;tot=0; } return 0; }
bzoj2286: [Sdoi2011]消耗战
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。