BZOJ-1574: [Usaco2009 Jan]地震损坏Damage

[文章目录]

Description

农夫John的农场遭受了一场地震.有一些牛棚遭到了损坏,但幸运地,所有牛棚间的路经都还能使用. FJ的农场有P(1 <= P <= 30,000)个牛棚,编号1..P. C(1 <= C <= 100,000)条双向路经联接这些牛棚,编号为1..C. 路经i连接牛棚a_i和b_i (1 <= a_i<= P;1 <= b_i <= P).路经可能连接a_i到它自己,两个牛棚之间可能有多条路经.农庄在编号为1的牛棚. N (1 <= N <= P)头在不同牛棚的牛通过手机短信report_j(2 <= report_j <= P)告诉FJ它们的牛棚(report_j)没有损坏,但是它们无法通过路经和没有损坏的牛棚回到到农场. 当FJ接到所有短信之后,找出最小的不可能回到农庄的牛棚数目.这个数目包括损坏的牛棚

贪心,如果一个点不可达,那么其周围的点要么不可达,要么损坏。既然要求最少的数目,直接损坏周围的点肯定是最优解(否则也不可达)。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,c,p,ans;
int head[31000],to[201000],nxt[201000],cnt;
void add(int x,int y)
{
    to[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}
queue<int>q;
bool vis[31000],v[31000];
void bfs()
{
    vis[1]=1; q.push(1);
    while(!q.empty())
    {
        ans++;
        int x=q.front(); q.pop();
        for(int i=head[x];i;i=nxt[i])
            if(!v[to[i]]&&!vis[to[i]])
                vis[to[i]]=1,q.push(to[i]);
    }
}
int main()
{
    scanf("%d%d%d",&p,&c,&n);
    int x,y;
    for(int i=1;i<=c;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    while(n--)
    {
        scanf("%d",&x);
        v[x]=1;
        for(int j=head[x];j;j=nxt[j])
            v[to[j]]=1;
    }
    bfs();
    printf("%d\n",p-ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注