UOJ14 DZY Loves Graph

DZY开始有

Add a b：表示在
Delete k：表示删除了当前图中边权最大的k条边。保证
Return：表示撤销第

请你在每次操作后告诉DZY当前图的最小生成树边权和。如果最小生成树不存在则输出

输入格式

第一行两个正整数

输入格式

对于每一个操作输出一行一个整数表示当前最小生成树边权和。

样例一

input

2 2
Add 1 2
Return

output

1
0

样例二

input

5 10
Add 2 1
Add 3 2
Add 4 2
Add 5 2
Add 2 3
Return
Delete 1
Add 2 3
Add 5 2
Return

output

样例三

见样例数据下载

正解：并查集+各种奇怪维护

解题报告：

　　调试了两个多小时才AC，而且还蒯了别人的题解。

　　传送门：http://vfleaking.blog.uoj.ac/blog/15

　　我讲不太清楚，直接看vfk的博客吧。

  1 //It is made by jump~
  2 #include <iostream>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <algorithm>
  8 #include <ctime>
  9 #include <vector>
 10 #include <queue>
 11 #include <map>
 12 #include <set>
 13 #ifdef WIN32   
 14 #define OT "%I64d"
 15 #else
 16 #define OT "%lld"
 17 #endif
 18 using namespace std;
 19 typedef long long LL;
 20 const int MAXM = 500011;
 21 int n,m,cnt;//cnt统计树边
 22 LL ans;
 23 int father[MAXM],last[MAXM];//分别表示最小生成树中的所在块的祖先和这条边断掉之后的所在块的祖先（前提，这条边在最小生成树中）
 24 //int stack[MAXM];
 25 int size[MAXM],top;
 26 char ch[12];
 27 LL num[MAXM];
 28 vector<int>q;
 29 struct ask{
 30     int type,x,y;
 31 }Q[MAXM];
 32 
 33 inline int getint()
 34 {
 35        int w=0,q=0;
 36        char c=getchar();
 37        while((c<'0' || c>'9') && c!='-') c=getchar();
 38        if (c=='-')  q=1, c=getchar();
 39        while (c>='0' && c<='9') w=w*10+c-'0', c=getchar();
 40        return q ? -w : w;
 41 }
 42 
 43 inline int find(int x){
 44     if(father[x]!=x) return find(father[x]);
 45     return father[x];
 46 }
 47 
 48 inline void delet(int x){
 49     int u;
 50     while(x--) {
 51     u=q[q.size()-1]; q.pop_back();
 52     //u=stack[top]; top--;
 53     if(last[u]!=-1) {
 54         ans-=u; cnt--;
 55         
 56         int y=father[u];
 57         while(y)
 58         {
 59             size[y]-=size[u];
 60             if(y==father[y]) break;
 61         }
 62         //if(father[x])  size[father[x]]-=size[x];
 63         father[last[u]]=last[u];
 64     }
 65     }
 66 }
 67 
 68 inline void work(){
 69     n=getint(); m=getint();
 70     for(int i=1;i<=m;i++) {
 71     scanf("%s",ch);
 72     if(ch[0]=='A')  Q[i].type=1,Q[i].x=getint(),Q[i].y=getint();
 73     else if(ch[0]=='D') Q[i].type=2,Q[i].x=getint();
 74     else Q[i].type=3;
 75     }
 76     for(int i=1;i<=n;i++) father[i]=i,size[i]=1;
 77     int x,y;
 78     for(int i=1;i<=m;i++) {
 79     if(Q[i].type==1) {
 80         //stack[++top]=i;
 81         q.push_back(i);
 82         x=find(Q[i].x); y=find(Q[i].y);
 83         if(x!=y) {//加入最小生成树，后面的肯定不如前面的编号小的更优
 84         if(size[x]>size[y]) swap(x,y);//交换，按秩
 85         last[i]=x; 
 86         father[x]=y; size[y]+=size[x];
 87         ans+=i; cnt++;
 88         }
 89         else last[i]=-1;//不在最小生成树中
 90     }
 91     else if(Q[i].type==2) {
 92         if(Q[i+1].type==3) {
 93         //printf("%lld
",num[top-Q[i].x]);
 94         printf("%lld
",num[q.size()-Q[i].x]);
 95         continue;
 96         }else delet(Q[i].x);
 97     }
 98     else {
 99         if(Q[i-1].type==1) delet(1);
100     }
101 
102     if(cnt==n-1) {//构成最小生成树
103         //num[top]=ans;
104         num[q.size()]=ans;
105         printf("%lld
",ans);
106     }
107     else { 
108         //num[top]=0;
109         num[q.size()]=0;
110         printf("0
"); }
111     }
112 }
113 
114 int main()
115 {
116   work();
117   return 0;
118 }