题解:洛谷 P14362 [CSP-S 2025] 道路修复
前置(?)
写的时候想到考试时居然没写出来，挺遗憾的。
思路
乍一看没什么思路，特殊性质 A 也有点误导，容易让人想成输出 \(0\) 。
当 \(k=0\) 时，思考一下，如果要最小化答案，对答案没贡献的边可以去掉，而为了两两连通，将有贡献的边留下，应该是一棵树，用最小生成树。
当 \(k \not= 0\) 时，其实也是跑最小生成树，但有些乡村是用不上的，而 \(k \le 10\) ，所以枚举要用的乡村。
但如果每次都排序不行，可以将所有的边存完后排序。
代码
#define ioss ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
ll n, m, k, f[N], c[N], minx=Inf;
struct node{ll w, a, b;bool operator<(const node& t)const{return w<t.w;}
};
vector<node> G;
int fd(int x){return (x!=f[x]?f[x]=fd(f[x]):x);//并查集
}
//Kruskal
int main(){//freopen("road.in","r",stdin);//freopen("road.out","w",stdout);ioss;//神秘快读，没有的话在洛谷只有96pts，很怪cin>>n>>m>>k;for(int i=1;i<=n+k;i++) f[i]=i;for(int i=1;i<=m;i++){int u, v, w;cin>>u>>v>>w;G.push_back({w, u, v});}sort(G.begin(),G.end());for(int i=1;i<=k;i++){cin>>c[i];for(int j=1;j<=n;j++){ll x;cin>>x;G.push_back({x,i+n,j});}}sort(G.begin(),G.end());int s=1<<k;for(int i=0;i<s;i++){//枚举2^kfor(int j=1;j<=n+k;j++) f[j]=j;vector<bool> vis(k+1);ll cnt=0, K=0, sum=0;for(int j=0;j<k;j++)if(i>>j&1){//位运算vis[j+1]=1;K++;sum+=c[j+1];}for(auto [w,u,v]:G){if(u>n&&!vis[u-n]||v>n&&!vis[v-n]) continue;u=fd(u);v=fd(v);if(u!=v){cnt++;sum+=w;if(u>n&&!vis[u-n]){sum+=c[u-n];}if(v>n&&!vis[v-n]){sum+=c[v-n];}f[u]=v;}if(cnt==K+n-1){break;}}cmin(minx, sum);}cout<<minx;
}