题解：
先用所有的边生成一棵最小生成树，然后从后往前不断删边，看此边有没有用到，用到的话重新跑生成树，没有的话结果不变。还是Kruskal方便些。。。
Prime:
#include <bits/stdc++.h> # define LL long long using namespace std; const int INF=0x7fffffff; int N,W; int dis[220]; int complete[220]; int used[6010]; int pre[220]; int removed; struct Edge{ int next; int to; int l; int id; }e[6010<<1]; int head[220]; int en; void add(int from, int to, int w, int id){ e[en].next=head[from]; e[en].to=to; e[en].l=w; e[en].id=id; head[from]=en; ++en; } int findmin(){ int mi=INF; int id=0; for(int i=1;i<=N;++i){ if(complete[i]==1) continue; if(dis[i]<mi){ mi=dis[i]; id=i; } } return id; } int prime(){ for(int i=1;i<=N;++i){ dis[i]=INF; } memset(complete,0,sizeof(complete)); memset(pre,-1,sizeof(pre)); memset(used,0,sizeof(used)); dis[1]=0; for(int i=1;i<=N-1;++i){ int u=findmin(); if(u==0) break; complete[u]=1; for(int j=head[u];j!=-1;j=e[j].next){ int v=e[j].to; int ei=e[j].id; if(ei>removed) continue; if(complete[v]==0 && e[j].l<dis[v]){ dis[v]=e[j].l; pre[v]=e[j].id; } } } int res=0; for(int i=1;i<=N;++i){ if(dis[i]==INF) return -1; res+=dis[i]; if(i>1){ used[pre[i]]=1; } } return res; } int main(){ memset(head,-1,sizeof(head)); scanf("%d %d", &N, &W); for(int i=1;i<=W;++i){ int u,v,w; scanf("%d %d %d", &u, &v, &w); add(u,v,w,i); add(v,u,w,i); } vector<int> res(W+1); removed=W; int t=prime(); if(t==-1){ for(int i=1;i<=W;++i){ printf("-1\n"); } return 0; } res[W]=t; for(int i=W-1;i>=1;--i){ removed=i; //大于removed的都删掉了 if(used[i+1]==1){ t=prime(); if(t==-1){ for(int j=i;j>=1;--j){ res[j]=-1; } break; } res[i]=t; }else{ res[i]=res[i+1]; } } for(int i=1;i<=W;++i){ printf("%d\n", res[i]); } return 0; }
Kruskal:
#include <bits/stdc++.h> # define LL long long using namespace std; const int INF=0x7fffffff; int N,W; int used[6010]; int removed[6010]; int parent[210]; struct Edge{ int from; int to; int l; int id; bool operator< (Edge e1){ return l<e1.l; } }e[6010]; int en; void add(int from, int to, int w, int id){ e[en].from=from; e[en].to=to; e[en].l=w; e[en].id=id; ++en; } int find(int p){ if(p==parent[p]) return p; parent[p]=find(parent[p]); return parent[p]; } int Kruskal(){ memset(used,0,sizeof(used)); for(int i=1;i<=N;++i) parent[i]=i; int sum=0; int cnt=0; for(int i=1;i<=W;++i){ int id=e[i].id; if(removed[id]==1) continue; int u=e[i].from; int v=e[i].to; int w=e[i].l; int fu=find(u); int fv=find(v); if(fu==fv) continue; cnt++; sum+=w; used[id]=1; parent[fu]=fv; if(cnt==N-1) return sum; } return -1; } int main(){ scanf("%d %d", &N, &W); en=1; for(int i=1;i<=W;++i){ int u,v,w; scanf("%d %d %d", &u, &v, &w); add(u,v,w,i); } sort(e+1,e+W+1); vector<int> res(W+1); int t=Kruskal(); if(t==-1){ for(int i=1;i<=W;++i){ printf("-1\n"); } return 0; } res[W]=t; for(int i=W-1;i>=1;--i){ removed[i+1]=1; if(used[i+1]==1){ t=Kruskal(); if(t==-1){ for(int j=i;j>=1;--j){ res[j]=-1; } break; } res[i]=t; }else{ res[i]=res[i+1]; } } for(int i=1;i<=W;++i){ printf("%d\n", res[i]); } return 0; }
原文：https://www.cnblogs.com/FEIIEF/p/12268244.html