「BZOJ2286」[SDOI2011] 消耗战

2015年1月20日8,1172

Description

在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。

侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到1号岛屿上）。不过侦查部门还发现了这台机器只能够使用m次，所以我们只需要把每次任务完成即可。

Input

第一行一个整数n，代表岛屿数量。

接下来n-1行，每行三个整数u,v,w，代表u号岛屿和v号岛屿由一条代价为c的桥梁直接相连，保证1<=u,v<=n且1<=c<=100000。

第n+1行，一个整数m，代表敌方机器能使用的次数。

接下来m行，每行一个整数k_i，代表第i次后，有k_i个岛屿资源丰富，接下来k个整数h₁,h₂,…h_k，表示资源丰富岛屿的编号。

Output

输出有m行，分别代表每次任务的最小代价。

Sample Input

10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6

Sample Output

12
32
22
「数据规模和约定」
对于10%的数据，2<=n<=10,1<=m<=5,1<=ki<=n-1
对于20%的数据，2<=n<=100,1<=m<=100,1<=ki<=min(10,n-1)
对于40%的数据，2<=n<=1000,m>=1,sigma(ki)<=500000,1<=ki<=min(15,n-1)
对于100%的数据，2<=n<=250000,m>=1,sigma(ki)<=500000,1<=ki<=n-1

题解

每次按照关键点的dfs序排序，维护栈构建一棵新的树，在新的树上dp

#include<iostream>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<stack>
#define inf 1e60
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int bin[20];
int n,m,cnt,ind,top;
int last[250005],last2[250005],fa[250005][20];
ll mn[250005],f[250005];
int h[250005],mark[250005],deep[250005];
int st[250005];
struct edge{
    int to,next,v;
}e[500005],ed[500005];
void insert(int u,int v,int w)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
    e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;
}
void insert2(int u,int v)
{
    if(u==v)return;
    ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;
}
bool cmp(int a,int b)
{
    return mark[a]<mark[b];
}
void pre(int x)
{
    mark[x]=++ind;
    for(int i=1;bin[i]<=deep[x];i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=last[x];i;i=e[i].next)
        if(e[i].to!=fa[x][0])
        {
            mn[e[i].to]=min(mn[x],(ll)e[i].v);
            deep[e[i].to]=deep[x]+1;
            fa[e[i].to][0]=x;
            pre(e[i].to);
        }
}
int lca(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    int t=deep[x]-deep[y];
    for(int i=0;bin[i]<=t;i++)
        if(t&bin[i])x=fa[x][i];
    for(int i=19;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    if(x==y)return x;
    return fa[x][0];
}
void dp(int x)
{
    f[x]=mn[x];
    ll tmp=0;
    for(int i=last2[x];i;i=ed[i].next)
    {
        dp(ed[i].to);
        tmp+=f[ed[i].to];
    }
    last2[x]=0;
    if(tmp==0)f[x]=mn[x];
    else if(tmp<=f[x])f[x]=tmp;
}
void solve()
{
    cnt=0;
    int K=read();
    for(int i=1;i<=K;i++)
        h[i]=read();
    sort(h+1,h+K+1,cmp);
    int tot=0;
    h[++tot]=h[1];
    for(int i=2;i<=K;i++)
        if(lca(h[tot],h[i])!=h[tot])h[++tot]=h[i];
    st[++top]=1;
    for(int i=1;i<=tot;i++)
    {
        int now=h[i],f=lca(now,st[top]);
        while(1)
        {
            if(deep[f]>=deep[st[top-1]])
            {
                insert2(f,st[top--]);
                if(st[top]!=f)st[++top]=f;
                break;
            }
            insert2(st[top-1],st[top]);top--;
        }
        if(st[top]!=now)st[++top]=now;
    }
    while(--top)insert2(st[top],st[top+1]);
    dp(1);
    printf("%lld\n",f[1]);
}
int main()
{
    bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read(),w=read();
        insert(u,v,w);
    }
    mn[1]=inf;pre(1);
    m=read();
    for(int i=1;i<=m;i++)
        solve();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include<iostream>

#include<set>

#include<map>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<cmath>

#include<bitset>

#include<stack>

#define inf 1e60

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int bin[20];

int n,m,cnt,ind,top;

int last[250005],last2[250005],fa[250005][20];

ll mn[250005],f[250005];

int h[250005],mark[250005],deep[250005];

int st[250005];

struct edge{

int to,next,v;

}e[500005],ed[500005];

void insert(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;

}

void insert2(int u,int v)

{

if(u==v)return;

ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;

}

bool cmp(int a,int b)

{

return mark[a]<mark[b];

}

void pre(int x)

{

mark[x]=++ind;

for(int i=1;bin[i]<=deep[x];i++)

fa[x][i]=fa[fa[x][i-1]][i-1];

for(int i=last[x];i;i=e[i].next)

if(e[i].to!=fa[x][0])

{

mn[e[i].to]=min(mn[x],(ll)e[i].v);

deep[e[i].to]=deep[x]+1;

fa[e[i].to][0]=x;

pre(e[i].to);

}

int lca(int x,int y)

{

if(deep[x]<deep[y])swap(x,y);

int t=deep[x]-deep[y];

for(int i=0;bin[i]<=t;i++)

if(t&bin[i])x=fa[x][i];

for(int i=19;i>=0;i--)

if(fa[x][i]!=fa[y][i])

x=fa[x][i],y=fa[y][i];

if(x==y)return x;

return fa[x][0];

}

void dp(int x)

{

f[x]=mn[x];

ll tmp=0;

for(int i=last2[x];i;i=ed[i].next)

{

dp(ed[i].to);

tmp+=f[ed[i].to];

}

last2[x]=0;

if(tmp==0)f[x]=mn[x];

else if(tmp<=f[x])f[x]=tmp;

}

void solve()

{

cnt=0;

int K=read();

for(int i=1;i<=K;i++)

h[i]=read();

sort(h+1,h+K+1,cmp);

int tot=0;

h[++tot]=h[1];

for(int i=2;i<=K;i++)

if(lca(h[tot],h[i])!=h[tot])h[++tot]=h[i];

st[++top]=1;

for(int i=1;i<=tot;i++)

{

int now=h[i],f=lca(now,st[top]);

while(1)

{

if(deep[f]>=deep[st[top-1]])

{

insert2(f,st[top--]);

if(st[top]!=f)st[++top]=f;

break;

}

insert2(st[top-1],st[top]);top--;

}

if(st[top]!=now)st[++top]=now;

}

while(--top)insert2(st[top],st[top+1]);

dp(1);

printf("%lld\n",f[1]);

}

int main()

{

bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;

n=read();

for(int i=1;i<n;i++)

{

int u=read(),v=read(),w=read();

insert(u,v,w);

}

mn[1]=inf;pre(1);

m=read();

for(int i=1;i<=m;i++)

solve();

return 0;

}

« 「BZOJ3696」「FJ2014集训」化合物「BZOJ3611」[HEOI2014] 大工程 »

( ⊙ o ⊙ )啊！

判断一个点是不是另一个点的后代，没必要LCA吧。直接dfs序就行了啊

hzwer

是的

hzwer.com _ Home | http://hzwer.com

「BZOJ2286」[SDOI2011] 消耗战

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论