|
试题描述
|
|
请你实现一个数据结构，完成这样的功能： 给你一个N个点的图，初始状态无边。 每次加入一条双向边(u,v,w)，若加入后没有构成一棵生成树，输出“Not Yet”，否则输出当前最小生成树的权值。 |
|
输入
|
|
第一行两个正整数N，M。表示有N个点M个操作。
接下来M行每行三个正整数u,v,w。 |
|
输出
|
|
每次加入一条双向边(u,v,w)，若加入后没有构成一棵生成树，输出“Not Yet”，否则输出当前最小生成树的权值。
|
|
输入示例
|
|
4 6
1 2 10 2 3 10 3 4 10 2 2 1 1 3 2 2 4 3 |
|
输出示例
|
|
Not Yet
Not Yet 30 30 22 15 |
|
其他说明
|
|
1<=N<=100000
1<=M<=500000 1<=ui,vi<=N 1<=wi<=1000 |
水水哒LCT，注意不要被坑
#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<algorithm>
#define lc ch[x][0]
#define rc ch[x][1]
#define rep(s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int ch[maxn][],val[maxn],fa[maxn],pre[maxn],mx[maxn],flip[maxn];
void maintain(int x) {
mx[x]=x;
if(val[mx[lc]]>val[mx[x]]) mx[x]=mx[lc];
if(val[mx[rc]]>val[mx[x]]) mx[x]=mx[rc];
}
void pushdown(int x) {
if(!flip[x]) return;
flip[x]=;flip[lc]^=;flip[rc]^=;
swap(lc,rc);
}
void rotate(int x) {
int y=pre[x],z=pre[y],d=ch[y][]==x;
ch[y][d^]=ch[x][d];pre[ch[x][d]]=y;
ch[z][ch[z][]==y]=x;pre[x]=z;
ch[x][d]=y;pre[y]=x;maintain(y);
}
int S[maxn],top;
void splay(int x) {
for(int i=x;i;i=pre[i]) S[++top]=i;
if(S[top]!=x) fa[x]=fa[S[top]];
while(top) pushdown(S[top--]);
while(pre[x]) rotate(x);
maintain(x);
}
void access(int x) {
for(int y=;x;x=fa[x]) {
splay(x);pre[ch[x][]]=;fa[ch[x][]]=x;
ch[x][]=y;pre[y]=x;maintain(y=x);
}
}
void makeroot(int x) {access(x);splay(x);flip[x]^=;}
void link(int x,int y) {makeroot(x);fa[x]=y;}
void cut(int x,int y) {
makeroot(x);access(y);splay(y);
pre[ch[y][]]=ch[y][]=;maintain(y);
}
int query(int x,int y) {makeroot(x);access(y);splay(y);return mx[y];}
int find(int x) {access(x);splay(x);while(ch[x][]) x=ch[x][];return x;}
int u[maxn],v[maxn];
int main() {
int n=read(),m=read(),ans=,cnt=n,ret=;
rep(,m) {
u[i]=read();v[i]=read();val[n+i]=read();
if(u[i]==v[i])
{
if(cnt==) printf("%d\n",ans);
else puts("Not Yet");
continue;
}
if(find(u[i])!=find(v[i])) cnt--,ans+=val[n+i],link(u[i],n+i),link(v[i],n+i);
else {
int t=query(u[i],v[i]);
if(val[t]>val[n+i]) {
cut(t,u[t-n]);cut(t,v[t-n]);
link(u[i],n+i);link(v[i],n+i);
ans-=val[t]-val[n+i];
}
}
if(cnt==) printf("%d\n",ans);
else puts("Not Yet");
}
return ;
}