首页 > > 程序设计 > C/C++ >

P1197 [JSOI2008]星球大战

2018-06-17 22:23:45来源：未知阅读 ()

题目描述

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。

但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。（如果两个星球可以通过现存的以太通道直接或间接地连通，则这两个星球在同一个连通块中）。

输入输出格式

输入格式：

输入文件第一行包含两个整数，N (1 <= N <= 2M) 和M (1 <= M <= 200,000)，分别表示星球的数目和以太隧道的数目。星球用0~N-1的整数编号。

接下来的M行，每行包括两个整数X, Y，其中（0<=X<>Y<N），表示星球X和星球Y之间有以太隧道。注意所有的以太隧道都是双向的。

接下来一行是一个整数K，表示帝国计划打击的星球个数。

接下来的K行每行一个整数X，满足0<=X<N，表示帝国计划打击的星球编号。帝国总是按输入的顺序依次摧毁星球的。

输出格式：

输出文件的第一行是开始时星球的连通块个数。

接下来的K行，每行一个整数，表示经过该次打击后现存星球的连通块个数。

输入输出样例

输入样例#1：

输出样例#1：

说明

[JSOI2008]

并查集的倒序使用，

一开始假设所有的星球全部摧毁

然后离线处理

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 using namespace std;
  6 void read(int & n)
  7 {
  8     char c='+';int x=0;
  9     while(c<'0'||c>'9')
 10     c=getchar();
 11     while(c>='0'&&c<='9')
 12     {
 13         x=x*10+(c-48);
 14         c=getchar();
 15     }
 16     n=x;
 17 }
 18 const int MAXN=400001;
 19 struct node
 20 {
 21     int u,v,nxt;
 22 }edge[MAXN];
 23 int head[MAXN];
 24 int num=1;
 25 int fa[MAXN];
 26 int n,m,t;
 27 void add_edge(int x,int y)
 28 {
 29     edge[num].u=x;
 30     edge[num].v=y;
 31     edge[num].nxt=head[x];
 32     head[x]=num++;
 33 }
 34 int vis[MAXN];
 35 int des[MAXN];
 36 int ans[MAXN];
 37 int find(int x)
 38 {
 39     if(fa[x]==x)
 40     return fa[x];
 41     else
 42     return fa[x]=find(fa[x]);
 43 }
 44 void unionn(int x,int y)
 45 {
 46     int fx=find(x);
 47     int fy=find(y);
 48     fa[fx]=fy;
 49 }
 50 int create(int p)
 51 {
 52     vis[p]=0;
 53     int x=0;
 54     for(int i=head[p];i!=-1;i=edge[i].nxt)
 55     {
 56         if(vis[edge[i].v]==0&&find(edge[i].u)!=find(edge[i].v))
 57         {
 58             unionn(edge[i].u,edge[i].v);
 59             x++;
 60         }
 61     }
 62     return x;
 63     
 64 }
 65 int vis2[MAXN];
 66 int calc()
 67 {
 68     memset(vis2,0,sizeof(vis2));
 69     int tot=0;
 70     for(int i=0;i<n;i++)
 71     {
 72         if(vis[i]==0&&find(i)==i)
 73         {
 74             //vis2[fa[i]]=1;
 75             tot++;
 76         }
 77     }
 78     return tot;
 79 }
 80 int main()
 81 {
 82     freopen("bzoj_1015.in","r",stdin);
 83     freopen("bzoj_1015.out","w",stdout);
 84     read(n);read(m);
 85     for(int i=0;i<n;i++)
 86         head[i]=-1,fa[i]=i;
 87     for(int i=0;i<m;i++)
 88     {
 89         int x,y;
 90         read(x);read(y);
 91         add_edge(x,y);add_edge(y,x);
 92     }
 93     read(t);
 94     for(int i=0;i<t;i++)
 95     {
 96         read(des[i]);
 97         vis[des[i]]=1;
 98     }
 99     for(int i=0;i<n;i++)
100     {
101         for(int j=head[i];j!=-1;j=edge[j].nxt)
102         if(vis[edge[j].u]==0&&vis[edge[j].v]==0)
103                 unionn(edge[j].u,edge[j].v);
104     }
105     ans[t]=calc();
106     for(int i=t-1;i>=0;i--)
107     {
108         int num=create(des[i]);
109         ans[i]=calc();
110     }
111     for(int i=0;i<=t;i++)
112     {
113         printf("%d\n",ans[i]);
114     }
115     return 0;
116 }

TLE代码

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 using namespace std;
  6 void read(int & n)
  7 {
  8     char c='+';int x=0;
  9     while(c<'0'||c>'9')
 10     c=getchar();
 11     while(c>='0'&&c<='9')
 12     {
 13         x=x*10+(c-48);
 14         c=getchar();
 15     }
 16     n=x;
 17 }
 18 const int MAXN=400001;
 19 struct node
 20 {
 21     int u,v,nxt;
 22 }edge[MAXN];
 23 int head[MAXN];
 24 int num=1;
 25 int fa[MAXN];
 26 int n,m,t;
 27 void add_edge(int x,int y)
 28 {
 29     edge[num].u=x;
 30     edge[num].v=y;
 31     edge[num].nxt=head[x];
 32     head[x]=num++;
 33 }
 34 int vis[MAXN];
 35 int des[MAXN];
 36 int ans[MAXN];
 37 int find(int x)
 38 {
 39     if(fa[x]==x)
 40     return fa[x];
 41     else
 42     return fa[x]=find(fa[x]);
 43 }
 44 void unionn(int x,int y)
 45 {
 46     int fx=find(x);
 47     int fy=find(y);
 48     fa[fx]=fy;
 49 }
 50 int create(int p)
 51 {
 52     vis[p]=0;
 53     int x=0;
 54     for(int i=head[p];i!=-1;i=edge[i].nxt)
 55     {
 56         if(vis[edge[i].v]==0&&find(edge[i].u)!=find(edge[i].v))
 57         {
 58             unionn(edge[i].u,edge[i].v);
 59             x++;
 60         }
 61     }
 62     return x;
 63     
 64 }
 65 int vis2[MAXN];
 66 int calc()
 67 {
 68     memset(vis2,0,sizeof(vis2));
 69     int tot=0;
 70     for(int i=0;i<n;i++)
 71     {
 72         if(vis[i]==0&&find(i)==i)
 73         {
 74             //vis2[fa[i]]=1;
 75             tot++;
 76         }
 77     }
 78     return tot;
 79 }
 80 int main()
 81 {
 82     freopen("bzoj_1015.in","r",stdin);
 83     freopen("bzoj_1015.out","w",stdout);
 84     read(n);read(m);
 85     for(int i=0;i<n;i++)
 86         head[i]=-1,fa[i]=i;
 87     for(int i=0;i<m;i++)
 88     {
 89         int x,y;
 90         read(x);read(y);
 91         add_edge(x,y);add_edge(y,x);
 92     }
 93     read(t);
 94     for(int i=0;i<t;i++)
 95     {
 96         read(des[i]);
 97         vis[des[i]]=1;
 98     }
 99     for(int i=0;i<n;i++)
100     {
101         for(int j=head[i];j!=-1;j=edge[j].nxt)
102         if(vis[edge[j].u]==0&&vis[edge[j].v]==0)
103                 unionn(edge[j].u,edge[j].v);
104     }
105     ans[t]=calc();
106     for(int i=t-1;i>=0;i--)
107     {
108         int num=create(des[i]);
109         ans[i]=ans[i+1]-num+1;
110     }
111     for(int i=0;i<=t;i++)
112     {
113         printf("%d\n",ans[i]);
114     }
115     return 0;
116 }