题目大意

最开始没有道路，每周会出现一条新的道路，求每一周出现新的道路后的最小生成树

 

思路

首先想到的是每次读入一条路径都去做一遍$Kruskal$，但是肯定会$T$成狗

翻了翻题解看到了$dalao$的做法

将$W$条边全部读入后

先对$W$条边做一遍$Kruskal$，然后从后往前倒着判断，这一周加的边是否在当前的MST中出现过

如果出现过，那就说明要重新做一遍$Kruskal$，知道无法找到$MST$，就可以$Break$了，既然现在找不到，那之前肯定也找不到

$%%% dalao %%%$

 

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int n, m, f[20800], Ans[600700], tot;bool book[600700], vis[600700];struct edge {    int u, v, w;    int num;}ed[600700];int find(int x) {    if(x == f[x]) return x;    else return f[x] = find(f[x]);}inline bool Kruskal(int s) {    memset(book, 0, sizeof(0));    tot = 0;    for(int i=1; i<=n; i++) f[i] = i;    for(int i=1; i<=m; i++) {        int xx = find(ed[i].u), yy = find(ed[i].v);        if(xx != yy && !vis[ed[i].num]) {            book[ed[i].num] = 1;            f[xx] = find(yy);            Ans[s] += ed[i].w;            tot++;        }        if(tot == n-1) {            return true;            break;        }    }    Ans[s] = -1;    return false;}inline bool cmp(edge a, edge b) {    return a.w < b.w;}int main() {    scanf("%d%d", &n, &m);    for(int i=1; i<=m; i++) {        scanf("%d%d%d", &ed[i].u, &ed[i].v, &ed[i].w);        ed[i].num = i;    }    sort(ed+1, ed+1+m, cmp);    bool mark;    Kruskal(m);    vis[m] = 1;    for(int i=m-1; i>=1; i--) {        vis[i+1] = 1;        if(book[i+1] == 1) {            mark = Kruskal(i);            if(!mark) {                for(int j=1; j