【JSOI2008】星球大战

2021-02-20 22:18

阅读：400

标签：time algorithm merge nbsp col problem com typedef ems

题目链接

直接算每次破坏会拆开多少个连通块貌似不可做。考虑反着加边用并查集合并。

那么我们首先用$vector$存下每个点出边到的点的序列。注意：$m\in[1,2\times 10^5]$而$n\in [1,2\times m]$所以$n\in [1,4\times 10^5]$。

读入破坏的顺序之后标记一下这些即将被破坏的点。

开始处理，首先用$BFS$连一下不会被破坏的点算连通块。注意：别连到了会被破坏的点（已经被标记），处理不好容易算重。

这里最好维护一下并查集要用的$f_i$和$sz_i$。注意：这里不用$DFS$的原因是内存只给了$125M$，处理不好容易爆栈$MLE$。

然后开始反向加边。注意：要求的是$0\sim k$时刻结束时的连通块计数，那么反向处理$i$时刻的结果就是原来$i-1$时刻的答案，自然反向加边之前的就是$k$时刻的答案。

时光逆流，每个时刻就有一个被光复的星球，没加边之前是孤立的，先把$cnt++$。

开始逐边恢复该星球的以太通讯，若目标不在同一个连通块内则有两个连通块合并，$cnt--$。注意：别向被破坏的点（有标记）连边。

恢复完毕该星球的以太通讯之后，把它的标记摘除。恭喜反抗军完成光复！【滑稽】

代码（100分）：

#include
#include
#include
#include
#include
#include
#include
#include
#includeset>
#define IL inline
#define RG register
#define _1 first
#define _2 second
using namespace std;
typedef unsigned int UI;
const int N=4e5;

    int n,m;
    vectorint>g[N+3];
    int k,a[N+3];
    bool p[N+3];
    
    int f[N+3],sz[N+3];
    int cnt;
    int s[N+3],hd,tl;

int find(int x){return (x==f[x])?x:(f[x]=find(f[x]));}

IL void merge(int x,int y){
    if(sz[x]sz[y])    swap(x,y);
    f[y]=x;    sz[x]+=(int)(sz[x]==sz[y]);
}

    int ans[N+3];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i){
        int u,v;    scanf("%d%d",&u,&v);
        u++;    v++;
        g[u].push_back(v);
        g[v].push_back(u);
        
    }
    scanf("%d",&k);
    memset(p,0,sizeof p);
    for(int i=1;i){
        scanf("%d",&a[i]);
        a[i]++;
        p[a[i]]=true;
        
    }
    
    for(int i=1;i){
        f[i]=i;    sz[i]=1;
    }
    cnt=0;
    for(int i=1;i)
    if(!p[i]&&f[i]==i){
        cnt++;
        s[hd=tl=1]=i;
        while(hdtl){
            int u=s[hd++];
            for(UI j=0;j){
                int v=g[u][j];
                if(f[v]==i||p[v])    continue;
                
                f[v]=i;
                sz[v]=sz[u]+1;
                sz[i]=max(sz[i],sz[v]);
                s[++tl]=v;
                
            }
            
        }
        
    }
        
    ans[k]=cnt;
    for(int i=k;i>=1;i--){
        cnt++;
        for(UI j=0;j)
        if(!p[g[a[i]][j]]){
            int x=find(a[i]),y=find(g[a[i]][j]);
            if(x!=y){
                merge(x,y);    cnt--;
            }
            
        }
        p[a[i]]=false;
        ans[i-1]=cnt;
        
    }
    
    for(int i=0;i)
        printf("%d\n",ans[i]);

    return 0;

}

View Code

【JSOI2008】星球大战

标签：time algorithm merge nbsp col problem com typedef ems

原文地址：https://www.cnblogs.com/Hansue/p/12913231.html

上一篇：HTTP接口请求

下一篇：Jquery与Bootstrap实现后台管理页面增删改查功能

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【JSOI2008】星球大战
文章链接：http://soscw.com/essay/58169.html

亲，登录后才可以留言！

【JSOI2008】星球大战

题目链接

评论

热门文章

推荐文章

最新文章

置顶文章