星球大战

来源

bzoj1015
JSOI2008

分析:

有一个同学做了PPT,里面的数据演示做得不错,详细做法建议看代码,更清晰
下载链接

题目

「问题描述」
很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。
某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。
这些星球通过特殊的以太隧道互相直接或间接地连接。
但好景不长,很快帝国又重新造出了他的超级武器。凭借这超级武器的力量,帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。
现在,反抗军首领交给你一个任务:
给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序,
以尽量快的速度求出每一次打击之后反抗军占据的星球的连通快的个数。
(如果两个星球可以通过现存的以太通道直接或间接地连通,则这两个星球在同一个连通块中)。
「问题大意」
给你一些点和边,有K次毁灭,每次删掉一条边,
输出没毁灭时的连通数以及每次操作后剩余的连通数量
「输入格式」
第一行包含两个整数,N(1<=N<=2M)和M(1<=M<= 200,000),分别表示星球的数目和以太隧道的数目。
星球用0~N-1的整数编号。接下来的M行,每行包括两个整数X, Y,其中(0<=X<>Y
「输出格式」
输出文件的第一行是开始时星球的连通块个数。
接下来的N行,每行一个整数,表示经过该次打击后现存星球的连通块个数。
「输入样例」
8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5 1 6 3 5 7
「输出样例」
1 1 1 2 3 3

代码

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
struct nod1
{
int hou;//最小儿子
int fa;//父亲
bool b;//是否会被炸毁
bool v;//是否存在
nod1() { hou=0;b=false;v=false; }
}point[400010];
struct nod2
{
int x;
int g;//哥哥
}road[400010];
/*
注意:
因为是双向路,
所以要开200000*2
*/
void bulid(int,int);
int findfa(int);
int add(int);

int f[400001];//这些点将被攻击
int ans[400001];//答案记录
//两个序列↑
int roadnum;
int sum;//连通块
int main(int argc, char *argv[])
{
int n,m;
cin>>n>>m;

for(int i=0;i<n;i++) point[i].fa=i;//初始化每个点的父亲为自己

roadnum=0;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
bulid(x,y);
bulid(y,x);//建边
}
int k;
cin>>k;
for(int i=1;i<=k;i++)
{
cin>>f[i];
point[f[i]].b=true;//如果不会被炸毁的先标记下来下边可以用上
}
//倒推大法↓
sum=0;
for(int i=0;i<n;i++)//是0到n-1
{
if(point[i].b==false)//没被炸毁的先建边
{
sum++;
add(i);
point[i].v=true;//建了边代表存在的
}
}
ans[k+1]=sum;//k+1代表最后炸毁的状态
for(int i=k;i>0;i--)//模拟,一个一个把点加上去
{
sum++;
add(f[i]);//加点
point[f[i]].v=true;//这条边存在
ans[i]=sum;//记录值
}
for(int i=1;i<=k+1;i++) printf("%d\n",ans[i]);
}
int add(int n)
{
int xf=findfa(n);
for(int k=point[n].hou;k>0;k=road[k].g)//这个点应该加在哪里
{
int x=road[k].x;
if(point[x].v==true)//存在
{
int yf=findfa(x);
if(xf!=yf)
{
point[yf].fa=n;
sum--;//如果祖先不一样的话,统一祖先,连通块-1
}
}
}
}
void bulid(int x,int y)
{
roadnum++;
road[roadnum].x=y;
road[roadnum].g=point[x].hou;
point[x].hou=roadnum;
}
int findfa(int x)
{
if(x!=point[x].fa) point[x].fa=findfa(point[x].fa)
return point[x].fa;
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/4cfd.html
转载请注明出处,谢谢!