[vijos1070]新年趣事之遊戲（次小生成樹）

傳送門

我用的最原始的辦法：

先求最小生成樹然後枚舉删除一條最小生成樹上的邊

每次跑kruskal

然後時間就是 O(nm+mlogm)

有人會問為什麼沒有那個log

因為每次隻要打個删除标記，就可以避免重新排序，就可以降下來複雜度了

還有更高效的做法，一會兒再補，現在要去上課了（滑稽）

代碼：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ll long long
#define R register
using namespace std;
inline int read(){
    int x=;char ch=' ';int f=;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')f=-,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*+ch-'0',ch=getchar();
    return x*f;
}
const int N=;
struct edge{
    int x,y,w;
    inline bool operator < (const edge& b) const {
        return w<b.w;
    }
}e[N*N];
int n,m,del,ans=;
int id[N],fa[N],tot,cnt;
inline int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void solve(){
    for(int i=;i<=n;i++)fa[i]=i;
    int num=;cnt=n;
    for(int i=;i<=m;i++){
        if(del==i)continue;
        int u=find(e[i].x);int v=find(e[i].y);
        if(u==v)continue;
        fa[u]=v;
        num+=e[i].w;
        cnt--;
        if(cnt==)break;
    }
    if(cnt!=)return;
    ans=min(ans,num);
}
int main(){
    n=read();m=read();
    for(int i=;i<=n;i++)fa[i]=i;
    for(int i=;i<=m;i++){
        e[i].x=read();e[i].y=read();e[i].w=read();
    }
    sort(e+,e+m+);
    int num=;cnt=n;
    for(int i=;i<=m;i++){
        int u=find(e[i].x);int v=find(e[i].y);
        if(u==v)continue;
        fa[u]=v;
        num+=e[i].w;
        id[++tot]=i;
        cnt--;
        if(cnt==)break;
    }
    if(cnt!=){
        printf("Cost: -1\nCost: -1");
        return ;
    }
    printf("Cost: %d\n",num);
    for(int i=;i<=tot;i++){
        del=id[i];
        solve();
    }
    if(ans==){
        printf("Cost: -1");
    }
    else{
        printf("Cost: %d",ans);
    }
    return ;
}