首页 > 代码库 > BZOJ 1574: [Usaco2009 Jan]地震损坏Damage
BZOJ 1574: [Usaco2009 Jan]地震损坏Damage
题目
1574: [Usaco2009 Jan]地震损坏Damage
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 415 Solved: 226
[Submit][Status]
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接到所有短信之后,找出最小的不可能回到农庄的牛棚数目.这个数目包括损坏的牛棚. 注意:前50次提交将提供在一些测试数据上的运行结果.
Input
* 第1行: 三个空格分开的数: P, C, 和 N
* 第2..C+1行: 每行两个空格分开的数: a_i 和 b_i * 第C+2..C+N+1行: 每行一个数: report_j
Output
* 第1行: 一个数,最少不能回到农庄的牛的数目(包括损坏的牛棚).
Sample Input
4 3 1
1 2
2 3
3 4
3
1 2
2 3
3 4
3
Sample Output
3
HINT
牛棚2遭到损坏,导致牛棚2, 3, 4里面的牛无法回到农庄.
Source
Gold
题解
呃，这题就是一旦某个牧场没有损坏了但是无法到达，那么和它连的边应该都死了，所以一遍dfs就可以了！
代码
1 /*Author:WNJXYK*/ 2 #include<cstdio> 3 using namespace std; 4 5 struct Edge{ 6 int v; 7 int nxt; 8 Edge(){} 9 Edge(int a,int c){10 v=a;nxt=c;11 }12 };13 Edge e[200005];14 int nume;15 int head[30010];16 bool del[30010];17 int n,c,ans,w; 18 19 inline void addSingleEdge(int x,int y){20 e[++nume]=Edge(y,head[x]);21 head[x]=nume;22 }23 inline void addEdge(int x,int y){24 addSingleEdge(x,y);25 addSingleEdge(y,x);26 }27 bool visited[30010];28 void dfs(int x){29 ans--;30 visited[x]=true;31 for (int i=head[x];i;i=e[i].nxt){32 if (visited[e[i].v]==false && del[e[i].v]==false) dfs(e[i].v);33 }34 }35 int main(){36 scanf("%d%d%d",&n,&c,&w);37 for (int i=1;i<=c;i++){38 int x,y;39 scanf("%d%d",&x,&y);40 addEdge(x,y);41 }42 for (int i=1;i<=w;i++){43 int x;44 scanf("%d",&x);45 for (int j=head[x];j;j=e[j].nxt){46 del[e[j].v]=true;47 }48 }49 ans=n;50 dfs(1);51 printf("%d\n",ans);52 return 0;53 }
BZOJ 1574: [Usaco2009 Jan]地震损坏Damage
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。