「BZOJ1574」[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接到所有短信之后,找出最小的不可能回到农庄的牛棚数目.这个数目包括损坏的牛棚. 注意:前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里面的牛无法回到农庄.
题解
随便搜索
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #define inf 0x7fffffff #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int p,c,n,cnt,ans; bool del[30005],mark[30005]; struct data{int to,next;}e[200005];int head[30005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt; } void dfs(int x) { ans--; mark[x]=1; for(int i=head[x];i;i=e[i].next) if((!mark[e[i].to])&&(!del[e[i].to]))dfs(e[i].to); } void dele(int x) { for(int i=head[x];i;i=e[i].next) del[e[i].to]=1; } int main() { p=read();c=read();n=read(); for(int i=1;i<=c;i++) { int u=read(),v=read(); insert(u,v);insert(v,u); } ans=p; for(int i=1;i<=n;i++) { int x=read();dele(x); } dfs(1); printf("%d",ans); return 0; } |
Subscribe
计数器 9788581
OI 课件=>
OI 课件=>