我的解法：启发式并查集+状态建树
观察题目的三种操作
1. Add a b: 表示在 a 与 b 之间连了一条长度为 i 的边(注意, i是操作编号)。保证 1≤a,b≤n。
2.Delete k: 表示删除了当前图中边权最大的k条边。保证 k 一定不会比当前图中边的条数多。
3.Return: 表示撤销第 i−1 次操作。保证第 1 次操作不是 Return 且第 i−1次不是 Return 操作。
发现：
Add操作均是从上一个状态转移加边;
Delete相当于将状态转移到k条边之前
Return则是上上次状态
发现这个状态其实是一棵树
我直接将这个树建了出来
对于每个点来说，其实它加边的情况就是根节点到它的路径
所以dfs时入栈加边，出栈删边即可
接下来我们讨论加、删边操作---->
首先，这道题边权从小到大给出，所以可以直接类似Kruskal地加边，并查集维护(极其显然)
并查集加边想必没有问题，那如何维护删边呢？
我用(向)了(大佬)一(学习)种(了)启发式并查集(按秩合并)，不使用路径压缩来维护
我们通常并查集压缩路径后是O(1)复杂度，但是如果放弃路径合并，每次更新就只有一次更改
放弃路径合并的话，如何保证复杂度？
记录当前并查集子树的最大深度，每次将深度小的集合接上去
这样最坏情况下是深度是log(n)，保证了查询复杂度
至此，问题就解决了
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i) #define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i) char IO; inline int rd(){ int s=0; while(!isdigit(IO=getchar())); do s=(s<<1)+(s<<3)+(IO^'0'); while(isdigit(IO=getchar())); return s; } const int N=3e5+10,M=5e5+10; struct Edge{ int to,nxt; }e[M]; int head[M],ecnt; inline void AddEdge(int u,int v){ e[++ecnt]=(Edge){v,head[u]}; head[u]=ecnt; } #define erep(u,i) for(int i=head[u];i;i=e[i].nxt) int n,m,cnt; ll ans; int opt[M],a[M],b[M]; int q[M],r,now[M]; int f[M]; int d[M],t[M]; int dep[N],fa[N]; inline int Find(int x){ while(x!=fa[x]) x=fa[x]; return x; } void merge(int x,int y,int w){ x=Find(x),y=Find(y); if(x==y) return; if(dep[x]>dep[y]) swap(x,y); fa[x]=y; d[w]=y,t[w]=dep[y],f[w]=x;//记录更改的值 dep[y]=(dep[y]<dep[x]+1)?dep[x]+1:dep[y]; cnt--,ans+=w; } ll res[M]; void dfs(int u){ merge(a[u],b[u],u);//加边 if(cnt<=1) res[u]=ans; else res[u]=0; erep(u,i) { int v=e[i].to; dfs(v); } if(f[u]) ans-=u,cnt++,dep[d[u]]=t[u],fa[f[u]]=f[u];//删除 } inline void wt(ll x){ int buf[21],l=0; while(x) buf[++l]=x,x/=10; drep(i,l,1) putchar('0'^buf[i]); putchar('\n'); } int main(){ n=rd(),m=rd(); rep(i,1,n) fa[i]=i; cnt=n; rep(i,1,m) { char s[10]; scanf("%s",s); if(s[0]=='A') opt[i]=1,a[i]=rd(),b[i]=rd(); else if(s[0]=='D') opt[i]=2,a[i]=rd(); else opt[i]=3; } rep(i,1,m) { if(opt[i]==1){ AddEdge(now[i-1],i); now[i]=q[++r]=i;//维护状态树 } else if(opt[i]==2) now[i]=q[(r-=a[i])]; else { if(opt[i-1]==1) r--; else r+=a[i-1]; now[i]=now[i-2]; } } dfs(1); rep(i,1,m){ if(opt[i]^1) res[i]=res[now[i]]; if(res[i]) wt(res[i]); else puts("0"); } } ```转载于:https://www.cnblogs.com/chasedeath/p/11308404.html
相关资源：JAVA上百实例源码以及开源项目