Solution-P14362

· · 题解

讲一讲自己的考场思路。

首先发现题目中有“任意两座城市都能通过若干条道路相互到达。”这样一句话，说明我们大概率需要求出原图最小生成树。求出原图最小生成树后，你会发现其他边无论如何都是没用的，因此我们把边数缩减到了 n-1。

然后我们发现 k\le10，这允许我们 O(2^k) 枚举对哪些乡镇进行城市化改造，结合把这些边加进原图的最小生成树后再求最小生成树即可。时间复杂度 O(m\log m+2^kkn\log n)。

复杂度带一只 \log 不知道能不能过，所以尝试优化。我们先对每个乡镇连出的 n 条边按边权从小到大排序，然后由于原图最小生成树的边也是按边权从小到大排序的，我们相当于需要合并 k+1 个有序数列，归并即可。时间复杂度 O(m\log m+kn\log n+2^kk^2n\alpha(n))，但是跑不满，可以优化归并的部分做到把 k^2 去掉。

代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int u,v,w;
}p[1000001],t[10001],a[11][10001],h[1000001],tmp[1000001];
int n,m,k,f[10011],c[11],cnt,siz,x,y;
long long res,ans;
vector<int>u;
inline bool cmp(node _1,node _2){
    return _1.w<_2.w;
}
inline int find(int i){
    return f[i]==i?i:f[i]=find(f[i]);
}
inline void dfs(int i){
    if(i==k+1){
        siz=n-1;
        res=0;
        for(int j=1;j<=siz;j++){
            h[j]=t[j];
        }
        for(int j:u){
            res+=c[j];
            merge(h+1,h+siz+1,a[j]+1,a[j]+n+1,tmp+1,cmp);
            siz+=n;
            for(int l=1;l<=siz;l++){
                h[l]=tmp[l];
            }
        }
        for(int j=1;j<=n+k;j++){
            f[j]=j;
        }
        for(int j=1;j<=siz;j++){
            x=find(h[j].u);
            y=find(h[j].v);
            if(x!=y){
                f[x]=y;
                res+=h[j].w;
            }
        }
        ans=min(ans,res);
        return;
    }
    for(int j=i+1;j<=k+1;j++){
        if(j!=k+1){
            u.push_back(j);
        }
        dfs(j);
        if(j!=k+1){
            u.pop_back();
        }
    }
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>p[i].u>>p[i].v>>p[i].w;
    }
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    sort(p+1,p+m+1,cmp);
    for(int i=1;i<=m;i++){
        x=find(p[i].u);
        y=find(p[i].v);
        if(x!=y){
            f[x]=y;
            cnt++;
            t[cnt]=p[i];
            ans+=p[i].w;
        }
    }
    for(int i=1;i<=k;i++){
        cin>>c[i];
        for(int j=1;j<=n;j++){
            cin>>a[i][j].w;
            a[i][j].u=n+i;
            a[i][j].v=j;
        }
        sort(a[i]+1,a[i]+n+1,cmp);
    }
    dfs(0);
    cout<<ans;
    return 0;
}