[CSP-S 2025] 道路修复 / road

· · 题解

前言

还是输在蓝题了，不过好像不是输的那么彻底，还能翻盘吗？——失败了，我怎么这么弱，被杀穿了。

题目分析

首先注意到 m 条边中不在最小生成树里的一定没有用，这条边一定可以被其它边代替。求一遍最小生成树可以把 m 去掉，这部分时间复杂度 O(m\log m)，可以使用 Kruskal。

我们对剩下 k 个乡镇不好处理（由于不需要用的乡镇不应该加点权），考虑枚举，每次做暴力最小生成树，这部分时间复杂度是 O(2^knk\log nk)。

考虑瓶颈在哪里？——排序。整体排序即可，时间复杂度 O(m\log m+2^k nk)。但我没想到这个东西，所以写的是随机化暴力。

代码

先给一份随机化暴力的代码，这个不保证能通过。

#include<bits/stdc++.h>
#define int long long
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define ALL(x) x.begin(),x.end()
using namespace std;
constexpr int N=1e4+11,M=1e6+1;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
__inline void read(int&x){
    x=0;
    char ch=getchar();
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch))
        x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return;
}
void write(int x){
    if(x>=10)
        write(x/10);
    putchar((x%10)^48);
    return;
}
int n,m,k,fa[N],siz[N],ans,edcnt,cst[11],wal[11][N],st=clock(),perm[11]={0,1,2,3,4,5,6,7,8,9,10};
//vector<pair<int,int> >e[N];
vector<tuple<int,int,int> >edges,tmp;
void initdsu(int nn){
    for(int i=0;i<=nn;i++)
        fa[i]=i,siz[i]=1;
    return;
}
__inline int findfa(int x){
    int tmp=x,xx=x;
    while(fa[tmp]!=tmp)
        tmp=fa[tmp];
    while(fa[x]!=tmp)
        x=fa[x],
        fa[x]=tmp;
    return fa[xx]=tmp;
}
__inline bool cmp(const tuple<int,int,int>&a,const tuple<int,int,int>&b){
    return(get<2>(a))<(get<2>(b));
}
int kruskal(const int&cnt,const int&pt){
    int res=pt;
    edcnt=0;
    initdsu(n+k);
    sort(ALL(edges),cmp);
    for(auto ed:edges){
        int u=(get<0>(ed)),v=(get<1>(ed)),w=(get<2>(ed)),fau=findfa(u),fav=findfa(v);
        if(fau!=fav){
            edcnt++;
            res+=w;
            if(siz[fau]>siz[fav])
                swap(fau,fav);
            fa[fau]=fav,siz[fav]+=siz[fau];
        }
        if(edcnt==n+cnt-1||res>=ans)
            break;
    }
    return res;
}
signed main(){
    read(n),read(m),read(k);
    for(int i=1,u,v,w;i<=m;i++){
        read(u),read(v),read(w);
        edges.push_back(make_tuple(u,v,w));
    }
    for(int i=1;i<=k;i++){
        read(cst[i]);
        for(int j=1;j<=n;j++)
            read(wal[i][j]);
    }
    initdsu(n);
    sort(ALL(edges),cmp);
    for(auto ed:edges){
        int u=(get<0>(ed)),v=(get<1>(ed)),w=(get<2>(ed)),fau=findfa(u),fav=findfa(v);
        if(fau!=fav){
            edcnt++;
            ans+=w;
            if(siz[fau]>siz[fav])
                swap(fau,fav);
            siz[fav]+=siz[fau];
            fa[fau]=fav;
            tmp.push_back(ed);
        }
        if(edcnt==n-1)
            break;
    }
    shuffle(perm+1,perm+k+1,rng);
    for(int s=1,res,cnt;s<(1<<k);s++){
        res=cnt=0,edges=tmp;
        for(int i=1;i<=k;i++)
            if((s>>(i-1))&1){
                int v=perm[i];
                res+=cst[v],cnt++;
                for(int j=1;j<=n;j++)
                    edges.push_back(make_tuple(n+v,j,wal[v][j]));
            }
        ans=min(ans,kruskal(cnt,res));
        if(1.0*(clock()-st)/CLOCKS_PER_SEC>1.98)
            break;
    }
    write(ans);
    return 0;
}

再放一份正解代码：

#include<bits/stdc++.h>
#define int long long
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#define ALL(x) x.begin(),x.end()
using namespace std;
constexpr int N=1e4+11,M=1e6+1;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
__inline void read(int&x){
    x=0;
    char ch=getchar();
    while(!isdigit(ch))
        ch=getchar();
    while(isdigit(ch))
        x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return;
}
void write(int x){
    if(x>=10)
        write(x/10);
    putchar((x%10)^48);
    return;
}
int n,m,k,fa[N],siz[N],ans,edcnt,cst[11],wal[11][N],st=clock(),perm[11]={0,1,2,3,4,5,6,7,8,9,10};
//vector<pair<int,int> >e[N];
vector<tuple<int,int,int> >edges,tmp;
void initdsu(int nn){
    for(int i=0;i<=nn;i++)
        fa[i]=i,siz[i]=1;
    return;
}
__inline int findfa(int x){
    int tmp=x,xx=x;
    while(fa[tmp]!=tmp)
        tmp=fa[tmp];
    while(fa[x]!=tmp)
        x=fa[x],
        fa[x]=tmp;
    return fa[xx]=tmp;
}
__inline bool cmp(const tuple<int,int,int>&a,const tuple<int,int,int>&b){
    return(get<2>(a))<(get<2>(b));
}
int kruskal(const int&cnt,const int&pt,int s){
    int res=pt;
    edcnt=0;
    initdsu(n+k);
//  sort(ALL(edges),cmp);
    for(auto ed:edges){
        int u=(get<0>(ed)),v=(get<1>(ed)),w=(get<2>(ed));
        if((u<=n||u>n&&((s>>((u-n)-1))&1))&&(v<=n||v>n&&((s>>((v-n)-1))&1)));
        else continue;
        int fau=findfa(u),fav=findfa(v);
        if(fau!=fav){
            edcnt++;
            res+=w;
            if(siz[fau]>siz[fav])
                swap(fau,fav);
            fa[fau]=fav,siz[fav]+=siz[fau];
        }
        if(edcnt==n+cnt-1||res>=ans)
            break;
    }
    return res;
}
signed main(){
    read(n),read(m),read(k);
    for(int i=1,u,v,w;i<=m;i++){
        read(u),read(v),read(w);
        edges.push_back(make_tuple(u,v,w));
    }
    for(int i=1;i<=k;i++){
        read(cst[i]);
        for(int j=1;j<=n;j++)
            read(wal[i][j]);
    }
    initdsu(n);
    sort(ALL(edges),cmp);
    for(auto ed:edges){
        int u=(get<0>(ed)),v=(get<1>(ed)),w=(get<2>(ed)),fau=findfa(u),fav=findfa(v);
        if(fau!=fav){
            edcnt++;
            ans+=w;
            if(siz[fau]>siz[fav])
                swap(fau,fav);
            siz[fav]+=siz[fau];
            fa[fau]=fav;
            tmp.push_back(ed);
        }
        if(edcnt==n-1)
            break;
    }
    edges=tmp;
    for(int i=1;i<=k;i++)
        for(int j=1;j<=n;j++)
            edges.push_back(make_tuple(n+i,j,wal[i][j]));
    sort(ALL(edges),cmp);
    for(int s=1,res,cnt;s<(1<<k);s++){
        res=cnt=0;
        for(int i=1;i<=k;i++)
            if((s>>(i-1))&1)
                res+=cst[i],cnt++;
        ans=min(ans,kruskal(cnt,res,s));
    }
    write(ans);
    return 0;
}