1. 首页
  2. 杂文
  3. 正文

bzoj1015:[JSOI2008]星球大战starwar【并查集】

  • 内容
  • 评论
  • 相关

题目点击这里

直接按照读入的顺序处理会很不方便，所以我们可以采用离线的方式，先把所有的输入读进来，然后倒过来处理最后一起输出就可以了。

至于具体的方法，从最后倒过来，记录到最后剩下的星球，然后按照最后的样子加入边之类的，用并查集处理联通块数量，然后原本摧毁了哪个星球就按相反的顺序加入星球和对应的边。

代码：

var
  f,s,a,num,v,next,ans:array[0..400001]of longint;
  b:array[0..400000]of boolean;
  n,m,i,j,k,t,p,q:longint;
function getfather(i:longint):longint;
begin
  if f[i]=-1 then exit(i)
  else f[i]:=getfather(f[i]);
  exit(f[i]);
end;
procedure union(p,q:longint);
var
  x,y:longint;
begin
  x:=getfather(p);
  y:=getfather(q);
  if x=y then exit;
  dec(t);
  if num[x]<=num[y] then
  begin
    f[y]:=x;
    num[x]:=num[x]+num[y];
  end
  else begin
    f[x]:=y;
    num[y]:=num[x]+num[y];
  end;
end;
procedure adde(uu,vv:longint);
begin
  inc(k);
  v[k]:=vv;
  next[k]:=a[uu];
  a[uu]:=k;
  inc(k);
  v[k]:=uu;
  next[k]:=a[vv];
  a[vv]:=k;
end;
begin
  read(n,m);
  fillchar(f,sizeof(f),255);
  for i:=1 to m do
  begin
    read(p,q);
    adde(p,q);
  end;
  read(k);
  fillchar(b,sizeof(b),true);
  for i:=1 to k do
  begin
    read(s[i]);
    b[s[i]]:=false;
  end;
  t:=n-k;
  for i:=0 to n-1 do
  if b[i] then
  begin
    j:=a[i];
    while j<>0 do
    begin
      if b[v[j]] then union(i,v[j]);
      j:=next[j];
    end;
    ans[k+1]:=t;
  end;
  for i:=k downto 1 do
  begin
    j:=a[s[i]];
    inc(t);
    while j<>0 do
    begin
      if b[v[j]] then union(s[i],v[j]);
      j:=next[j];
    end;
    ans[i]:=t;
    b[s[i]]:=true;
  end;
  for i:=1 to k+1 do writeln(ans[i]);
end.

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。