首页 > Web开发 > 详细

BZOJ [JSOI2008]星球大战starwar

时间:2018-01-12 23:34:24      阅读:103      评论:0      收藏:0      [点我收藏+]

标签:print   name   ans   贪心   !=   blog   printf   spa   const   

正着显然不可做,我们采取反向并查集,将删点改为加点,每次贪心的认为加了一个联通块,一旦不符就减一。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=4e6+10;
 4 bool del[N],v[N];
 5 int f[N],p[N],head[N],cnt,tot,ans[N],n,m,k;
 6 int get(int x){return x==f[x]?x:f[x]=get(f[x]);}
 7 struct node{
 8     int to,nex;
 9 }e[N];
10 void addd(int x,int y){e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt;}
11 void add(int x)
12 {
13     int fx=get(x);
14     for(int i=head[x];i;i=e[i].nex)
15     {
16         int y=e[i].to;
17         if(v[y])
18         {
19             int fy=get(y);
20             if(fy!=fx)f[fy]=fx,tot--;
21         }
22     }
23 }
24 int main()
25 {
26     scanf("%d%d",&n,&m);int x,y;
27     for(int i=1;i<=n;++i)f[i]=i;
28     for(int i=1;i<=m;++i)
29     {
30         scanf("%d%d",&x,&y);
31         addd(x,y);addd(y,x);
32     }
33     scanf("%d",&k);
34     for(int i=1;i<=k;++i)
35     {
36         scanf("%d",&p[i]);
37         del[p[i]]=1;
38     }
39     for(int i=0;i<n;++i)
40     {
41         if(!del[i])
42         {
43             tot++;
44             add(i);
45             v[i]=1;
46         }
47     }
48     ans[0]=tot;
49     for(int i=k;i;--i)
50     {
51         tot++;
52         add(p[i]);
53         v[p[i]]=1;
54         ans[k-i+1]=tot;
55     }
56     for(int i=k;i>=0;--i)printf("%d\n",ans[i]);
57     return 0;
58 }

 

BZOJ [JSOI2008]星球大战starwar

标签:print   name   ans   贪心   !=   blog   printf   spa   const   

原文:https://www.cnblogs.com/nbwzyzngyl/p/8277838.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号