bzoj 1015 //1015: [JSOI2008]星球大战starwar //在线测评地址https://www.lydsy.com/JudgeOnline/problem.php?id=1015
更多题解，详见https://blog.csdn.net/mrcrack/article/details/90228694BZOJ刷题记录
10200 kb1704 msC++/Edit1248 B//1015: [JSOI2008]星球大战starwar //在线测评地址https://www.lydsy.com/JudgeOnline/problem.php?id=1015 //题意很快明白，模拟了样例，输入输出数据也对上了。 //朴素做法，删除一个节点，重新做一次并查集。2M+(2M-1)+(2M-2)+......+1肯定超时。 //该题的难点在于，删除节点的处理。2019-10-31 //该题考并查集无疑，还要加上什么技巧呢？ //此文http://hzwer.com/1695.html思路不错，摘抄如下： /* 给定一张图，支持删点和询问连通块个数 按操作顺序处理的话要在删除点的同时维护图的形态（即图具体的连边情况），这是几乎不可做的 我们发现，这道题可以先读入操作，把没删的点的边先连上，然后再倒序处理操作 这样的话从删点变成了加点，而且只要维护连通块的数量，用并查集可以快速的解决这个问题 */ //样例通过，提交Time_Limit_Exceed 8632 kb 3000 ms C++/Edit 1342 B .2019-10-31 //以下为Time_Limit_Exceed代码。
//此文https://www.luogu.org/problemnew/solution/P1197 作者: XSamsara 更新时间: 2017-12-21 15:29 代码写得够短，思路太棒了。 /* 读完题目，我们首先会想到每次删去一个点，然后重新建图，算出联通块的个数。然而，这根本不信，时间上过不去，这时就得让我们将头旋转180度，从后往前处理，也就是我们经常用的接边了。当然，再接边前需要预处理，当前这条边应当在什么时候接上，给边标上序号，然后依次处理。最后逆序输出，就可以啦啦啦。如果还不懂，请看代码。
PS：帝国攻占的地盘不算是反抗军的地盘。 */ //一个比较重要的技巧是找联通块个数，详见代码。 //孤立的星球开始，每联通一个，孤立星球就减少一个。 //在下面部分，排查了很长时间。j,i部分，敏感度太低了。 /* merge(e[j].x,e[j].y);//此处错写成merge(e[i].x,e[i].y);//此处错写成merge(e[i].x,e[i].y),ans[K-i]=num-(K-i);//K-i个被摧毁的星球 */ //样例通过，提交Output_Limit_Exceed 10200 kb 304 ms C++/Edit 1206 B. 2019-10-31 20:41 //排查代码，发现，测试代码未删除。 /* if(f1!=f2)f[f2]=f1,num--;//此处错写成if(f1!=f2)f[f2]=f1,num--,printf("u=%d v=%d num=%d\n",u,v,num); */ //样例通过，提交AC. 2019-10-31 20:44 #include <cstdio> #include <algorithm> #include <cstring> #define maxm 200100 #define maxn 400100 using namespace std; struct node{ int x,y,c; }e[maxn];//c越小越先处理。 int N,M,K; int vis[maxn],num,ans[maxn],f[maxn]; int max(int a,int b){ return a>b?a:b; } int cmp(node a,node b){//自小到大排序 return a.c<b.c; } int getf(int u){ return f[u]==u?u:f[u]=getf(f[u]); } void merge(int u,int v){ int f1=getf(u),f2=getf(v); if(f1!=f2)f[f2]=f1,num--;//此处错写成if(f1!=f2)f[f2]=f1,num--,printf("u=%d v=%d num=%d\n",u,v,num); } int main(){ int i,j,a; memset(vis,0,sizeof(vis)); scanf("%d%d",&N,&M),num=N; for(i=1;i<=M;i++)scanf("%d%d",&e[i].x,&e[i].y); scanf("%d",&K); for(i=1;i<=K;i++)scanf("%d",&a),vis[a]=K-i+1; for(i=1;i<=M;i++)e[i].c=max(vis[e[i].x],vis[e[i].y]); sort(e+1,e+1+M,cmp); for(i=0;i<=N;i++)f[i]=i; for(i=0,j=1;i<=K;i++){ for(;e[j].c==i;j++) merge(e[j].x,e[j].y);//此处错写成merge(e[i].x,e[i].y);//此处错写成merge(e[i].x,e[i].y),ans[K-i]=num-(K-i); ans[K-i]=num-(K-i);//K-i个被摧毁的星球 } for(i=0;i<=K;i++)printf("%d\n",ans[i]); return 0; }
//1015: [JSOI2008]星球大战starwar //在线测评地址https://www.lydsy.com/JudgeOnline/problem.php?id=1015 //题意很快明白，模拟了样例，输入输出数据也对上了。 //朴素做法，删除一个节点，重新做一次并查集。2M+(2M-1)+(2M-2)+......+1肯定超时。 //该题的难点在于，删除节点的处理。2019-10-31 //该题考并查集无疑，还要加上什么技巧呢？ //此文http://hzwer.com/1695.html思路不错，摘抄如下： /* 给定一张图，支持删点和询问连通块个数 按操作顺序处理的话要在删除点的同时维护图的形态（即图具体的连边情况），这是几乎不可做的 我们发现，这道题可以先读入操作，把没删的点的边先连上，然后再倒序处理操作 这样的话从删点变成了加点，而且只要维护连通块的数量，用并查集可以快速的解决这个问题 */ //样例通过，提交Time_Limit_Exceed 8632 kb 3000 ms C++/Edit 1342 B .2019-10-31 //以下为Time_Limit_Exceed代码。 #include <stdio.h> #include <string.h> #define maxm 200100 int vis[maxm<<1],x[maxm],y[maxm],n,m,k,q[maxm<<1],f[maxm<<1],ans[maxm<<1]; int getf(int u){ return f[u]==u?u:f[u]=getf(f[u]); } void merge(int u,int v){ int f1=getf(u),f2=getf(v);//此处错写成int f1=getf(f[u]),f2=getf(f[v]); if(f1!=f2)f[f2]=f1;//左靠 } int main(){ int i,cnt=0,j; memset(vis,0,sizeof(vis)); scanf("%d%d",&n,&m); for(i=1;i<=m;i++)scanf("%d%d",&x[i],&y[i]); scanf("%d",&k); for(i=1;i<=k;i++)scanf("%d",&q[i]),vis[q[i]]=1; for(i=0;i<n;i++)f[i]=i;//此处错写成for(i=0;i<=n;i++)f[i]=i; for(i=1;i<=m;i++) if(vis[x[i]]==0&&vis[y[i]]==0) merge(x[i],y[i]); cnt=0; for(i=0;i<n;i++)//此处错写成for(i=1;i<=n;i++) if(vis[i]==0&&f[i]==i)cnt++;//此处错写成if(f[i]==i)cnt++; ans[k+1]=cnt; for(i=k;i>=1;i--){ vis[q[i]]=0;//漏了此行 for(j=1;j<=m;j++) if((x[j]==q[i]||y[j]==q[i])&&vis[x[j]]==0&&vis[y[j]]==0)//此处错写成if(x[j]==q[i]||y[j]==q[i]) merge(x[j],y[j]); cnt=0; for(j=0;j<n;j++)//此处错写成for(j=1;j<=n;j++) if(vis[j]==0&&f[j]==j)cnt++;//此处错写成if(f[j]==j)cnt++;//此处错写成if(f[i]==i)cnt++; ans[i]=cnt; } for(i=1;i<=k+1;i++)printf("%d\n",ans[i]); return 0; }
