好吃力的最小生成树

考场上爆0了（因为当时根本不会这算法，我当时都想到爆搜跑最小生成树了，诶）
1.直接跑最小生成树 16pts
2枚举每一个村庄见不见 爆搜32pts
大概就是长这样
32分代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,k,fa[10020],c[15],vis[15],sz[10020];
long long ans;
struct edge{int u,v,w;};
edge g[1000010];//原图
vector <edge> l;//新图
void init(){for(int i=1;i<=n+k;i++)fa[i]=i,sz[i]=1;}//注意初始化到n+k
int _find(int x){return fa[x]==x?x:fa[x]=_find(fa[x]);}
void _union(int x,int y){
    int fx=_find(x),fy=_find(y);
    if(fx==fy) return ;
    if(sz[fx]<sz[fy]) swap(fx,fy);
    fa[fy]=fx,sz[fx]+=sz[fy];
}//并查集操作
bool cmp(edge x,edge y){return x.w<y.w;}
void tree(){//新图跑最小生成树
    long long sum=0;
    for(int i=1;i<=k;i++){if(vis[i]){sum+=c[i];}}
    init();
    for(int i=0;i<l.size();i++){
        int u=l[i].u,v=l[i].v;
        if(u>n&&!vis[u-n]){continue;}
        if(_find(u)==_find(v)) continue;
        sum+=l[i].w;
        _union(u,v);
    }
    ans=min(ans,sum);
    return;
}
void dfs(int dep){
    if(dep>k){
        tree();
        return;
    }
    dfs(dep+1);
    vis[dep]=1;
    dfs(dep+1);
    vis[dep]=0;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);//这个要加 不加会爆
    cin>>n>>m>>k;
    init();
    for(int i=1;i<=m;i++){cin>>g[i].u>>g[i].v>>g[i].w;}
    sort(g+1,g+m+1,cmp);
    for(int i=1;i<=m;i++){//原图跑最小生成树
        int u=g[i].u,v=g[i].v;
        if(_find(u)==_find(v)) continue;
        _union(u,v);
        ans+=g[i].w;
        l.push_back(g[i]);
    }
    for(int j=1;j<=k;j++){//新边
        cin>>c[j];
        for(int i=1;i<=n;i++){
            int w;
            cin>>w;
            l.push_back({j+n,i,w});//村庄节点编号是n+j
        }
    }
    sort(l.begin(),l.end(),cmp);//提前排序
    dfs(1);
    cout<<ans;
    return 0;
}

接下来开始优化
1.最小生成树有一个性质：本来多余的边可以直接删
于是我们先跑一遍最小生成树 有用的边留在图里这样就去掉了每次爆搜中时间复杂度里面的m
2.这样每次爆搜里面复杂度2^k KNlogKN 我们要去掉复杂度里面的log
于是我们提前排好序 每次搜索只枚举点是否见，边可不可以用 取所有情况最小值即可
复杂度瓶颈：2^K KN
AC代码

#include <bits/stdc++.h>
using namespace std;
int n,m,k,fa[10020],c[15],vis[15],cnt;
long long ans;
struct edge{int u,v,w;};
edge g[1000010];//原图
vector <edge> l;//新图
void init(){for(int i=1;i<=n+k;i++)fa[i]=i;}//注意初始化到n+k
int _find(int x){return fa[x]==x?x:fa[x]=_find(fa[x]);}
void _union(int x,int y){
    int fx=_find(x),fy=_find(y);
    if(fx==fy) return ;
    fa[fx]=fy;
}//并查集操作
bool cmp(edge x,edge y){return x.w<y.w;}
void tree(){//新图跑最小生成树
    long long sum=0;
    cnt=0;
    for(int i=1;i<=k;i++){if(vis[i]){sum+=c[i],cnt--;}}//这里--代表有村庄要更多边
    init();
    for(int i=0;i<l.size();i++){
        if(cnt==n-1)break;
        int u=l[i].u,v=l[i].v;
        if(u>n&&!vis[u-n]){continue;}
        if(_find(u)==_find(v)) continue;
        sum+=l[i].w;
        _union(u,v);
        cnt++;
    }
    ans=min(ans,sum);
    return;
}
void dfs(int dep){
    if(dep>k){
        tree();
        return;
    }
    dfs(dep+1);
    vis[dep]=1;
    dfs(dep+1);
    vis[dep]=0;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);//这个要加 不加会爆
    cin>>n>>m>>k;
    init();
    for(int i=1;i<=m;i++){cin>>g[i].u>>g[i].v>>g[i].w;}
    sort(g+1,g+m+1,cmp);
    for(int i=1;i<=m;i++){//原图跑最小生成树
        if(cnt==n-1) break;
        int u=g[i].u,v=g[i].v;
        if(_find(u)==_find(v)) continue;
        _union(u,v);
        ans+=g[i].w;
        l.push_back(g[i]);
        cnt++;//这里我们使用这个cnt计数加了多少条边来卡常
    }
    for(int j=1;j<=k;j++){//新边
        cin>>c[j];
        for(int i=1;i<=n;i++){
            int w;
            cin>>w;
            l.push_back({j+n,i,w});//村庄节点编号是n+j
        }
    }
    sort(l.begin(),l.end(),cmp);//提前排序
    dfs(1);
    cout<<ans;
    return 0;
}

好毒瘤 谁天天去想这些优化
求赞