```
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[30000],hao[610000],ans[610000],t;
struct bian
{
int ch,d1,d2;//长，点1，点2
bool used;//是否在最小生成树中
bool cannotuse;//是否被删去
int id;
}b[610000];
bool cmp(bian a,bian b)
{
return a.ch<b.ch;
}
int find(int x)
{
if(x==fa[x]) return x;
else return fa[x]=find(fa[x]);
}
void build(int x)
{
b[x].used=1;
fa[find(b[x].d2)]=find(b[x].d1);
ans[t]=ans[t]+b[x].ch;
}
void kru()//kruskal
{
for(int i=1;i<=m;i++)
{
if(b[i].cannotuse==1||b[i].used==1)
{
continue;
}
if(find(b[i].d1)==find(b[i].d2))
{
continue;
}
else
{
build(i);
}
}
return;
}
int main()
{
scanf("%d%d",&n,&m);t=m;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&b[i].d1,&b[i].d2,&b[i].ch);
b[i].id=i;
}
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
sort(b+1,b+1+m,cmp);
for(int i=1;i<=m;i++)
{
hao[b[i].id]=i;
}
kru();t--;
for(int i=m-1;i>=1;i--)
{
b[hao[i+1]].cannotuse=1;
if(b[hao[i+1]].used==1)
{
for(int i=1;i<=m;i++) b[i].used=0;
for(int i=1;i<=n;i++) fa[i]=i;
kru();//kruskal
for(int i=1;i<n;i++)//判断图是否联通
{
if(fa[i]!=fa[i+1])
{
ans[t]=-1;
break;
}
}
}
t--;
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
```
by HKHbest @ 2019-03-01 19:09:32
样例过了不代表所有都过了啊
by pengzhaozhao @ 2020-08-02 15:57:14
我建议你用Prim或者Kruskal
by pengzhaozhao @ 2020-08-02 15:57:34