2012-0031

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意是有一个n个点m条边的图，敌人会随机选择一个点攻击，将与这个点相连的边都消灭，这个点的权值变成0。然后我们可以选择p个点保护，使得这些点如果被敌人攻击不会产生任何损失。
每个点都有一个权值，现在希望求在被攻击的最坏情况下，能够连到点S的点的权值和最大。
很显然，每个点如果被攻击，都会因为边的消失产生一个固定损失——因为这个点连出去的边消失使得与S相连的点数目减少导致权值和变小。
那么如果我们能够知道每个点被攻击造成的损失，就应该选择损失最大的p个来保护。
接下来，就是要求每个点的损失。
显然，根据连通性，一个点A被攻击之后会使得某一个点B无法与S连通，则这个点A必然是整个图的一个割点，且B在与S不同的一侧。
我们利用tarjan算法可以用o(n+m)的复杂度求出所有割点。其中，如果我们从S开始DFS，可以形成一棵DFS树，显然，如果A是一个割点，每一个由A点消失导致与S分开连通块，必然都是A的某一棵子树。因此我们可以在DFS时，用一个数组维护每个子树的权值和，然后在tarjan结束后，在每个点处判它的每个子树，是不是会因为这个点消失后与S不连通，如果是，就在这个点的损失值里加上这个子树的权值，其中损失值初值为这个点的权值。
最后只要将第p+1大的损失值输出就可以了。
然后有几点注意事项：
(1)、图中可能存在原本就与S不连通的区域，因此在DFS后，我们只去搜索被DFS扫描到的点，其它点都是不连通的，损失值应该设为0
(2)、如果p》=n，不会有任何损失值产生。

程序：
#include <cstdio>
#include <cstring>

int n,m,numk,sp,tot,t,o,p;
long long ans;
int x[20001],f[20001];
long long sum[20001],lose[20001],a[20001];
int low[20001],num[20001];
int y[200001],z[200001];

void add(int o,int p)
{
    tot++;
    y[tot]=p;
    z[tot]=x[o];
    x[o]=tot;
}

void dfs(int i)
{
    sum[i]=a[i];
    t++;
    low[i]=num[i]=t;
    for(int next=x[i];next;next=z[next])
    if(y[next]!=f[i])
    {
        if(num[y[next]]>n) 
        {
            f[y[next]]=i;
            dfs(y[next]);
            sum[i]=sum[i]+sum[y[next]];
            if(low[i]>low[y[next]]) low[i]=low[y[next]];
        } else
        if(low[i]>num[y[next]]) low[i]=num[y[next]];
    }

}

void kp(int s,int t)
{
    int i,j;
    long long m,o;
    i=s;j=t;
    m=lose[(s+t)/2];
    while(i<=j)
    {
        while(lose[i]>m) i++;
        while(lose[j]<m) j--;
        if(i<=j)
        {
            o=lose[i];lose[i]=lose[j];lose[j]=o;
            i++;j--;
        }
    }
    if(i<t) kp(i,t);
    if(s<j) kp(s,j);
}

int main()
{
    while(scanf("%d %d %d",&n,&m,&numk)!=EOF)
    {
        memset(x,0,sizeof(x));
        memset(f,0,sizeof(f));
        tot=0;
        for(int i=1;i<=n;i++) scanf("%lld",a+i);
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d",&o,&p);
            add(o,p);
            add(p,o);
        }
        scanf("%d",&sp);
        memset(low,0x70,sizeof(low));
        memset(num,0x70,sizeof(num));
        memset(lose,0,sizeof(lose));
        memset(sum,0,sizeof(sum));
        t=0;
        f[sp]=0;
        dfs(sp);    
        ans=sum[sp];
        for(int i=1;i<=n;i++)
        if(num[i]<=t)
        {
            lose[i]=a[i];
            for(int next=x[i];next;next=z[next])
            if((f[y[next]]==i)&&(num[i]<=low[y[next]]))
            lose[i]+=sum[y[next]];
        } else lose[i]=0;
        kp(1,n);
        if(numk<n) ans-=lose[numk+1];
        printf("%lld\n",ans);
    }
    return 0;
}




by hzwlzrj

题意是有一个n个点m条边的图，敌人会随机选择一个点攻击，将与这个点相连的边都消灭，这个点的权值变成0。然后我们可以选择p个点保护，使得这些点如果被敌人攻击不会产生任何损失。

每个点都有一个权值，现在希望求在被攻击的最坏情况下，能够连到点S的点的权值和最大。

很显然，每个点如果被攻击，都会因为边的消失产生一个固定损失——因为这个点连出去的边消失使得与S相连的点数目减少导致权值和变小。

那么如果我们能够知道每个点被攻击造成的损失，就应该选择损失最大的p个来保护。

接下来，就是要求每个点的损失。

显然，根据连通性，一个点A被攻击之后会使得某一个点B无法与S连通，则这个点A必然是整个图的一个割点，且B在与S不同的一侧。

我们利用tarjan算法可以用o(n+m)的复杂度求出所有割点。其中，如果我们从S开始DFS，可以形成一棵DFS树，显然，如果A是一个割点，每一个由A点消失导致与S分开连通块，必然都是A的某一棵子树。因此我们可以在DFS时，用一个数组维护每个子树的权值和，然后在tarjan结束后，在每个点处判它的每个子树，是不是会因为这个点消失后与S不连通，如果是，就在这个点的损失值里加上这个子树的权值，其中损失值初值为这个点的权值。

最后只要将第p+1大的损失值输出就可以了。

然后有几点注意事项：

(1)、图中可能存在原本就与S不连通的区域，因此在DFS后，我们只去搜索被DFS扫描到的点，其它点都是不连通的，损失值应该设为0

(2)、如果p》=n，不会有任何损失值产生。

程序：

#include

#include

int n,m,numk,sp,tot,t,o,p;

long long ans;

int x[20001],f[20001];

long long sum[20001],lose[20001],a[20001];

int low[20001],num[20001];

int y[200001],z[200001];

void add(int o,int p)

{

tot++;

y[tot]=p;

z[tot]=x[o];

x[o]=tot;

}

void dfs(int i)

{

sum[i]=a[i];

t++;

low[i]=num[i]=t;

for(int next=x[i];next;next=z[next])

if(y[next]!=f[i])

{

if(num[y[next]]>n)

{

f[y[next]]=i;

dfs(y[next]);

sum[i]=sum[i]+sum[y[next]];

if(low[i]>low[y[next]]) low[i]=low[y[next]];

} else

if(low[i]>num[y[next]]) low[i]=num[y[next]];

}

}

void kp(int s,int t)

{

int i,j;

long long m,o;

i=s;j=t;

m=lose[(s+t)/2];

while(i<=j)

{

while(lose[i]>m) i++;

while(lose[j]

if(i<=j)

{

o=lose[i];lose[i]=lose[j];lose[j]=o;

i++;j--;

}

}

if(i

if(s

}

int main()

{

while(scanf("%d %d %d",&n,&m,&numk)!=EOF)

{

memset(x,0,sizeof(x));

memset(f,0,sizeof(f));

tot=0;

for(int i=1;i<=n;i++) scanf("%lld",a+i);

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

{

scanf("%d %d",&o,&p);

add(o,p);

add(p,o);

}

scanf("%d",&sp);

memset(low,0x70,sizeof(low));

memset(num,0x70,sizeof(num));

memset(lose,0,sizeof(lose));

memset(sum,0,sizeof(sum));

t=0;

f[sp]=0;

dfs(sp);

ans=sum[sp];

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

if(num[i]<=t)

{

lose[i]=a[i];

for(int next=x[i];next;next=z[next])

if((f[y[next]]==i)&&(num[i]<=low[y[next]]))

lose[i]+=sum[y[next]];

} else lose[i]=0;

kp(1,n);

if(numk

printf("%lld\n",ans);

}

return 0;

}

by hzwlzrj