题目：csp-s2025T2
P14362 [CSP-S 2025] 道路修复 / road（民间数据）
题目背景
由于评测机性能差异，本题时限提升 1 秒。
测试数据未经过强度检验，可能存在错误做法获得较高分数，仅供参考。
题目描述
C 国的交通系统由 $n$ 座城市与 $m$ 条连接两座城市的双向道路构成，第 $i$ ($1 \leq i \leq m$) 条道路连接城市 $u_i$ 和 $v_i$。任意两座城市都能通过若干条道路相互到达。
然而，近期由于一场大地震，所有 $m$ 条道路都被破坏了，修复第 $i$ ($1 \leq i \leq m$) 条道路的费用为 $w_i$。与此同时，C 国还有 $k$ 个准备进行城市化改造的乡镇。对于第 $j$ ($1 \leq j \leq k$) 个乡镇，C 国对其进行城市化改造的费用为 $c_j$。在城市化改造完第 $j$ ($1 \leq j \leq k$) 个乡镇后，可以在这个乡镇与原来的 $n$ 座城市间建造若干条道路，其中在它与第 $i$ ($1 \leq i \leq n$) 座城市间建造一条道路的费用为 $a_{j,i}$。C 国可以在这 $k$ 个乡镇中选择任意多个进行城市化改造，也可以不选择任何乡镇进行城市化改造。
为尽快恢复城市间的交通，C 国政$ $府希望以最低的费用将原有的 $n$ 座城市两两连通，也即任意两座原有的城市都能通过若干条修复或新建造的道路相互到达。你需要帮助他们求出，将原有的 $n$ 座城市两两连通的最小费用。
输入格式
输入的第一行包含三个非负整数 $n, m, k$，分别表示原有的城市数量、道路数量和准备进行城市化改造的乡镇数量。
输入的第 $i+1$ ($1 \leq i \leq m$) 行包含三个非负整数 $u_i, v_i, w_i$，表示第 $i$ 条道路连接的两座城市与修复该道路的费用。
输入的第 $j+m+1$ ($1 \leq j \leq k$) 行包含 $n+1$ 个非负整数 $c_j, a_{j,1}, a_{j,2}, \ldots, a_{j,n}$，分别表示将第 $j$ 个乡镇进行城市化改造的费用与在该乡镇与原有的城市间建造道路的费用。
输出格式
输出一行一个非负整数，表示将原有的 $n$ 座城市两两连通的最小费用。
输入输出样例 #1
输入 #1
4 4 2
1 4 6
2 3 7
4 2 5
4 3 4
1 1 8 2 4
100 1 3 2 4
输出 #1
13
说明/提示
【样例 1 解释】
C 国政$ $府可以选择修复第 $3$ 条和第 $4$ 条道路，然后将第 $1$ 个乡镇进行城市化改造，并建造它与第 $1,3$ 座城市间的道路，总费用为 $5 + 4 + 1 + 1 + 2 = 13$。可以证明，不存在比 $13$ 更小的费用能使原有的 $4$ 座城市两两连通。
【样例 2】
见选手目录下的 $road/road2.in$ 与 $road/road2.ans$。
该样例满足测试点 $11,12$ 的约束条件。
【样例 3】
见选手目录下的 $road/road3.in$ 与 $road/road3.ans$。
该样例满足测试点 $13,14$ 的约束条件。
【样例 4】
见选手目录下的 $road/road4.in$ 与 $road/road4.ans$。
该样例满足测试点 $15,16$ 的约束条件。
【数据范围】
对于所有测试数据，保证：
- $1 \leq n \leq 10^4$，$1 \leq m \leq 10^6$，$0 \leq k \leq 10$;
- 对于所有 $1 \leq i \leq m$，均有 $1 \leq u_i, v_i \leq n$, $u_i \neq v_i$ 且 $0 \leq w_i \leq 10^9$;
- 对于所有 $1 \leq j \leq k$，均有 $0 \leq c_j \leq 10^9$;
- 对于所有 $1 \leq j \leq k$，$1 \leq i \leq n$, 均有 $0 \leq a_{j,i} \leq 10^9$;
- 任意两座原有的城市都能通过若干条原有的道路相互到达。
::cute-table{tuack}
| 测试点编号 | $n \leq$ | $m \leq$ | $k \leq$ | 特殊性质 |
|---|---|---|---|---|
| $1 \sim 4$ | $10^4$ | $10^6$ | $0$ | 无 |
| $5, 6$ | $10^3$ | $10^5$ | $5$ | A |
| $7, 8$ | ^ | ^ | ^ | 无 |
| $9, 10$ | ^ | $10^6$ | ^ | A |
| $11, 12$ | ^ | ^ | ^ | 无 |
| $13, 14$ | ^ | ^ | $10$ | A |
| $15, 16$ | ^ | ^ | ^ | 无 |
| $17, 18$ | $10^4$ | ^ | $5$ | A |
| $19, 20$ | ^ | ^ | ^ | 无 |
| $21 \sim 25$ | ^ | ^ | $10$ | ^ |
特殊性质 A：对于所有 $1 \leq j \leq k$，均有 $c_j = 0$ 且均存在 $1 \leq i \leq n$ 满足 $a_{j,i} = 0$。
思路：
kurskal，用小根堆给每条边排序，把乡镇连接的城市i，j看成一条i，j的路，边权为a_ik+c_k+a_kj。并且标记需要乡镇k这个中转站，加入堆中。跑kurskal时如果遇到需要中转站的边那就把乡镇城市化，并且把所有连边减去c_k当正常边加入到堆中。
代码
#include<bits/stdc++.h>
using namespace std;
int father[10005],n,m,k,c[15];
long long ans;
vector<long long>s[15];
struct edge{
int u,v;
long long w;
int p;
bool operator<(const edge &it)const{
return w>it.w;
}
};
priority_queue<edge> q;
int find(int x){
if(x==father[x])return x;
return father[x]=find(father[x]);
}
void unionn(int x,int y){
father[find(y)]=find(x);
return;
}
void kruskal(){
int kk=0;
while(!q.empty()){
int u=q.top().u;
int v=q.top().v;
long long w=q.top().w;
int p=q.top().p;
q.pop();
if(find(u)!=find(v)){
if(p>0){
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++)q.push({i,j,s[p][i-1]+s[p][j-1],0});
}
ans+=w;
unionn(u,v);
kk++;
}
if(kk==n-1)break;
}
return;
}
int main(){
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=n;i++)father[i]=i;
for(int i=1;i<=m;i++){
int u,v;
long long w;
scanf("%d %d %lld",&u,&v,&w);
q.push({u,v,w,0});
}
for(int i=1;i<=k;i++){
cin>>c[i];
for(int j=1;j<=n;j++){
long long w;
scanf("%lld",&w);
s[i].push_back(w);
}
for(int j=1;j<n;j++)
for(int k=j+1;k<=n;k++)
if(j!=k){
if(c[i]==0) q.push({j,k,s[i][j-1]+s[i][k-1],0});
else q.push({j,k,s[i][j-1]+c[i]+s[i][k-1],i});
}
}
kruskal();
cout<<ans;
return 0;
}
求问正确性
