而且我#2在本地跑也没问题
by watermonster @ 2020-10-08 18:27:07
???不是你码呢?/jk
by Ayanami_Rei @ 2020-10-08 18:43:59
@[Freedom_Cyclone](/user/133409) 不是给了提交记录吗？
by watermonster @ 2020-10-08 18:44:53
```
#include <cstdio>
using namespace std;
#define il inline
#define re register
const int N=500050;
char buf[(1<<21)+100],*p1=buf,*p2=buf;
il char get_char(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin))?EOF:*p1++;}
#define isdigit(ch) (ch>=48&&ch<=57)
il void read(int &x)
{
x=0;re char ch=get_char();
while(!isdigit(ch)) ch=get_char();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=get_char();
}
il void write(int x)
{
re int p=0;re char Tmp[100];
do{Tmp[++p]=x%10+48;}while(x/=10);
do{putchar(Tmp[p]);}while(--p);
}
il int max(int a,int b){return a>b?a:b;}
il void swap(int &a,int &b){a^=b^=a^=b;}
int fa[N],son[2][N],val[N],Max[N],tag[N];
#define ls(x) (son[0][x])
#define rs(x) (son[1][x])
#define ident(x,f) (rs(f)==x)
#define connect(x,f,s) (son[s][f]=x,fa[x]=f)
#define reverse(x) (swap(ls(x),rs(x)),tag[x]^=1)
#define notrt(x) (ls(fa[x])==x||rs(fa[x])==x)
il void pushup(int x)
{
Max[x]=x;
if(val[Max[ls(x)]]>val[Max[x]]) Max[x]=Max[ls(x)];
if(val[Max[rs(x)]]>val[Max[x]]) Max[x]=Max[rs(x)];
}
il void pushdown(int x)
{
if(!tag[x]) return;tag[x]=0;
if(ls(x)) reverse(ls(x));
if(rs(x)) reverse(rs(x));
}
il void rotate(int x)
{
re int f=fa[x],ff=fa[f],k=ident(x,f);
connect(son[k^1][x],f,k);
fa[x]=ff;
if(notrt(f)) son[ident(f,ff)][ff]=x;
connect(f,x,k^1);
pushup(f);pushup(x);
}
int st[N],top;
il void pushall(int x)
{
top=0;
while(notrt(x)) st[++top]=x,x=fa[x];
pushdown(x);
while(top) pushdown(st[top--]);
}
il void splay(int x)
{
pushall(x);
while(notrt(x))
{
re int f=fa[x],ff=fa[f];
if(notrt(f)) rotate(ident(f,ff)^ident(x,f)?x:f);
rotate(x);
}
}
il void access(int x)
{
for(re int i=0;x;x=fa[i=x])
splay(x),rs(x)=i,pushup(x);
}
#define makert(x) (access(x),splay(x),reverse(x))
il int getrt(int x)
{
access(x),splay(x);
while(ls(x)){pushdown(x),x=ls(x);}
splay(x);return x;
}
#define link(u,v) (makert(u),fa[u]=v)
#define split(u,v) (makert(u),access(v),splay(v))
int n,m,ans,tot;
int main()
{
read(n),read(m);
tot=n;
for(re int i=1,u,v,w;i<=m;++i)
{
read(u),read(v),read(w);
if(u==v) continue;
val[++tot]=w;Max[tot]=tot;
makert(u);
if(getrt(v)^u){ans+=w;link(u,tot);link(v,tot);}
else
{
split(u,v);re int p=Max[v];
if(val[p]>w)
{
ans-=val[p]-w;
splay(p);
fa[ls(p)]=fa[rs(p)]=0;
link(u,tot);link(v,tot);
}
}
}
write(ans);
return 0;
}
```
by watermonster @ 2020-10-08 18:45:24
**不是dalao你这是什么算法/jk**
本蒟kruskal瑟瑟发抖
by Ayanami_Rei @ 2020-10-08 18:48:43
可以看下我以前写的 <https://www.luogu.com.cn/record/38686244>
by hly1204 @ 2020-10-08 22:33:05