P14362题解

· · 题解

:::warning[给管理大大]{open} 因为现存的几篇题解中没有详细的数学证明，所以我来补充一下，希望通过，感谢管理。 ::: 谨以此篇——致我即将退役的 OI 生涯......

题目分析

首先不难发现我们可以枚举修复乡村的集合，然后跑一遍 Kruskal 生成树。

但这个时间复杂度是 O(2^k(kn+m)\log(kn+m))，其中 n\le10^4,m\le10^6,k\le10，我们承受不起只能考虑优化。

性质分析

最小生成树具有如下性质：

一条边 e 不在原图 G 的最小生成树中的充要条件是存在环 C 使 e 是环 C 中边权最大的边。

此性质显然成立。

那么根据上述性质，如果一条边 e 不在原图 G 的最小生成树中，图中必然存在一个包含 e 的环 C，且 e 是该环上权重最大的边。

那么在添加新边形成新图 G' 后，e 在环 C 依然是最大边权的边，因此 e 也不可能出现在 G' 的最小生成树中。

换而言之，如果一条边 e 不在原图 G 的最小生成树中，那么添加新边形成 G' 后，e 也不可能出现在 G' 的最小生成树中。

那么回归原先的优化，我们可以对原先的 m 条边跑一次 Kruskal，筛出有用的 n-1 条边，再暴力枚举修复乡村的 2^k 种情况各自跑 Kruskal 即可，如果一开始将 n-1+kn 条边预处理排序可以把复杂度降到 O(m\log(m)+kn\log(kn)+2^kkn\alpha(n+k))。

:::success[思考完再看]


#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define M 1000006
#define N 10014
void read(int &x){
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return ;
}
struct edge{
    int u,v,w;
    bool operator <(const edge &b)const{
        return w<b.w;
    }
}e[M<<1];
int etot=0,ecnt=0;
int n,m,k,fa[N],u,v,w,cst[11];
ll ans=0;bool ok[11];
int findfa(int x){
    if(fa[x]!=x) fa[x]=findfa(fa[x]);
    return fa[x];
}
int main(){
    read(n);read(m);read(k);
    for(int i=1;i<=m;i++){
        read(e[i].u);read(e[i].v);read(e[i].w);
    }
    sort(e+1,e+m+1);
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        u=e[i].u,v=e[i].v,w=e[i].w;
        if(findfa(u)!=findfa(v)){
            ecnt++;
            ans+=w;
            fa[fa[u]]=fa[v];
            etot++;
            e[etot]=e[i];
            if(ecnt==n-1) break;
        }
    }
    for(int i=1;i<=n+k;i++) fa[i]=i;
    for(int i=1;i<=k;i++){
        read(cst[i]);
        for(int j=1;j<=n;j++){
            etot++;
            read(e[etot].w);
            e[etot].u=j;e[etot].v=i+n;
        }
    }
    sort(e+1,e+etot+1);
    //for(int i=1;i<=etot;i++) cerr<<e[i].u<<" "<<e[i].v<<" "<<e[i].w<<"\n";
    ll ret=0;
    int cnt=0,po=0;
    for(int flag=1;flag<(1<<k);flag++){
        ret=0;cnt=0;po=0;ecnt=0;
        for(int j=1;j<=n+k;j++) fa[j]=j;
        for(int j=1;j<=k;j++){
            if(flag&(1<<(j-1))){
                po++;
                ok[j]=true;
                ret+=cst[j];
            }
            else ok[j]=false;
        }
        if(ret>ans) continue;
        for(int i=1;i<=etot;i++){
            u=e[i].u,v=e[i].v,w=e[i].w;
            if(v>n&&!ok[v-n]) continue;
            if(findfa(u)!=findfa(v)){
                //cerr<<u<<" "<<v<<" "<<w<<"\n";
                ecnt++;
                ret+=w;
                fa[fa[u]]=fa[v];
                if(ecnt==n+po-1) break;
                if(ret>=ans) break;
            }
        }
        //cerr<<ret;
        if(ret<ans) ans=ret;
    }
    printf("%lld",ans);
    return 0;
}
:::