Miku

这题目很water

只要按照题意模拟就行了，数据似乎没有重边，那么对于加入每一条边的时候，如果两端点没联通，那么连上，反之

先连上，形成一个环，去点环上最大的边

数据范围不大对

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int head[3000001];
int x,y,z;
int n,m;
int p;
int vis[6000001];
int re[6000001];
struct b{
    int f;
    int to;
    int ne;
    int v;  
}ed[6000001];
void add(int f,int to,int v){
    p++;
    ed[p].to=to;
    ed[p].ne=head[f];
    ed[p].f=f;
    ed[p].v=v;  ;
    head[f]=p;
    p++;
    re[p-1]=p;
    re[p]=p-1;
    ed[p].to=f;
    ed[p].ne=head[to];
    ed[p].f=to;
    ed[p].v=v;
    head[to]=p;
    return ;
}
int fa[400001];
int find(int x){
    return x==fa[x]? x:fa[x]=find(fa[x]);
}
int cnt;
int f;
int ans;
int res;
void dfs(int now,int aim,int maxx,int la){
    if(f)
    return ;
    if(now==aim){
        f=1;
        res=maxx;
        return ;
    }
    for(int i=head[now];i;i=ed[i].ne){
        if(!vis[i]&&!vis[re[i]]&&ed[i].to!=la){
            //dfs(ed[i].to,aim,max(maxx,ed[i].v),now);
            if(ed[i].v>ed[maxx].v)
            dfs(ed[i].to,aim,i,now);
            else
            dfs(ed[i].to,aim,maxx,now);
        }
    }
}
void work(int x,int y,int z){
    if(find(x)!=find(y)){
        fa[fa[x]]=fa[y];
        add(x,y,z);
        cnt++;
        ans+=z;
    }else{
        f=0;
        dfs(x,y,0,0);
        if(ed[res].v>=z){
            add(x,y,z);
            ans+=z-ed[res].v;
            vis[res]=vis[re[res]]=1;
        }
    }
    if(cnt!=n-1){
        cout<<-1<<endl;
        return ;
    }else{
        cout<<ans<<endl;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        fa[i]=i;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&x,&y,&z);
        work(x,y,z);
        }
    return 0;
}