首先依次加边,直到整个图联通为止,之前均输出,
图刚连通时跑一遍正常的克鲁斯卡尔。
然后将用到的边存起来(只有条),
之后每加一条边,就对将这条边排序,
再跑就可以了。
复杂度(快排)
(插入排序)
#include<algorithm> #include<iostream> #include<cstdio> #define rep(i,a,b) for(int i=(a);i<=(b);i++) using namespace std; const int maxn=25000; struct Bian{ int a,b,v; bool operator <(const Bian &bb)const{ return v<bb.v; } }bian[100000],dq[100000]; int n,ci,zt,ji,Ans,fa[maxn]; int find(int e){return fa[e]=(fa[e]==e)?(e):(find(fa[e]));} int main(){ scanf("%d%d",&n,&ci); rep(i,1,n)fa[i]=i;ji=n; rep(i,1,ci){ if(zt==0){ scanf("%d%d%d",&bian[i].a,&bian[i].b,&bian[i].v); int faa=find(bian[i].a),fab=find(bian[i].b); if(faa!=fab){ fa[faa]=fab; ji--; } if(ji==1){ zt=1; rep(j,1,n)fa[j]=j; sort(bian+1,bian+i+1); Ans=0;int tot=0; rep(j,1,i){ faa=find(bian[j].a),fab=find(bian[j].b); if(faa!=fab){ dq[++tot]=bian[j]; fa[faa]=fab; Ans+=bian[j].v; } } printf("%d\n",Ans); continue; } else{ printf("-1\n"); continue; } } else{ scanf("%d%d%d",&dq[n].a,&dq[n].b,&dq[n].v); sort(dq+1,dq+n+1); rep(j,1,n)fa[j]=j; Ans=0; int de; rep(j,1,n){ int faa=find(dq[j].a),fab=find(dq[j].b); if(faa!=fab){ fa[faa]=fab; Ans+=dq[j].v; } else de=j; } rep(j,de,n-1)dq[j]=dq[j+1]; printf("%d\n",Ans); } } return 0; }