A19507. 道路修复（road）
题目描述
道路修复（road）
题目描述
C 国的交通系统由 n 座城市与 m 条连接两座城市的双向道路构成，第 i（1 ≤ i ≤ m）条道路连接城市 ui 和 vi。任意两座城市都能通过若干条道路相互到达。
然而，近期由于一场大地震，所有 m 条道路都被破坏了，修复第 i（1 ≤ i ≤ m）条道路的费用为 wi。与此同时，C 国还有 k 个准备进行城市化改造的乡镇。对于第 j（1 ≤ j ≤ k）个乡镇，C 国对其进行城市化改造的费用为 cj。在城市化改造完第 j（1 ≤ j ≤ k）个乡镇后，可以在这个乡镇与原来的 n 座城市间建造若干条道路，其中在它与第 i（1 ≤ i ≤ n）座城市间建造一条道路的费用为 aj,i。C 国可以在这 k 个乡镇中选择任意多个进行城市化改造，也可以不选择任何乡镇进行城市化改造。
为尽快恢复城市间的交通，C 国政府希望以最低的费用将原有的 n 座城市两两连通，也即任意两座原有的城市都能通过若干条修复或新建造的道路相互到达。你需要帮助他们求出，将原有的 n 座城市两两连通的最小费用。
输入格式
从文件 road.in 中读入数据。
输入的第一行包含三个非负整数 n, m, k，分别表示原有的城市数量、道路数量和准备进行城市化改造的乡镇数量。
输入的第 i+1（1 ≤ i ≤ m）行包含三个非负整数 ui, vi, wi，表示第 i 条道路连接的两座城市与修复该道路的费用。
输入的第 j+m+1（1 ≤ j ≤ k）行包含 n+1 个非负整数 cj, aj,1, aj,2,..., aj,n，分别表示将第 j 个乡镇进行城市化改造的费用与在该乡镇与原有的城市间建造道路的费用。
输出格式
输出到文件 road.out 中。
输出一行一个非负整数，表示将原有的 n 座城市两两连通的最小费用。
样例 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 ≤ n ≤ 104，1 ≤ m ≤ 106，0 ≤ k ≤ 10；
对于所有 1 ≤ i ≤ m，均有 1 ≤ ui, vi ≤ n，ui ≠ vi 且 0 ≤ wi ≤ 109；
对于所有 1 ≤ j ≤ k，均有 0 ≤ cj ≤ 109；
对于所有 1 ≤ j ≤ k，1 ≤ i ≤ n，均有 0 ≤ aj,i ≤ 109；
任意两座原有的城市都能通过若干条原有的道路相互到达。
特殊性质A:
对于所有1 ≤ j ≤ k，均有cj =0且均存在1≤i≤n满足 aj,i =0。
参考答案
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4 + 5;
const int MAXM = 1e6 + 5;
//快速读入
inline int read() {
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
//边结构体
struct edge{
int u, v;
int w; //边权
};
int n, m, k;
vector<edge> OG; //原图
vector<edge> NG; //新图
int c[11]; //乡镇改造费用
int fa[MAXN+10]; //并查集
bool z[11]; //标记乡镇是否被选中
//按边权排序
bool cmp(edge x, edge y) { return x.w < y.w; }
// 标准并查集操作
int findroot(int x) { return fa[x] == x ? x : fa[x] = findroot(fa[x]); }
void merge(int x, int y) {
x = findroot(x);
y = findroot(y);
fa[x] = y;
}
//第一次kruskal，用于求出s=0的答案，并删去m条边中后续不可能被选中的边
long long kruskal_first() {
for (int i = 1; i <= n; i++) fa[i] = i; //并查集初始化
long long res = 0;
int cnt = n - 1; //需要选取n-1条
for (edge i : OG) {
if (!cnt) return res; //选完就退出
int x = findroot(i.u), y = findroot(i.v);
if (x != y) {
merge(x, y); //合并
cnt--;
res += i.w;
NG.push_back(i); //将第一次MST选中的边加入新图
}
}
return res;
}
//加入乡镇后的MST
long long kruskal(int s) {
for (int i = 1; i <= n+k; i++) fa[i] = i; //并查集初始化
memset(z, 0, sizeof z); //标记数组初始化
long long res = 0;
int cnt = n - 1;
for (int i = 0, j = 1; i < k; i++, j <<= 1) {
if (s & j) { //按二进制拆分状态
z[i] = 1;
res += c[i];
cnt++;
}
}
for (edge i : NG) {
if (!cnt) return res;
//如果边的连接点有乡镇，需要判断边是否存在
if ((i.u > n && !z[i.u-n-1]) || (i.v > n && !z[i.v-n-1])) continue;
int x = findroot(i.u), y = findroot(i.v);
if (x != y) {
merge(x, y);
cnt--;
res += i.w;
}
}
return res;
}
int main() {
int u, v, w;
n = read();
m = read();
k = read();
for (int i = 0; i < m; i++) {
u = read();
v = read();
w = read();
OG.push_back({u, v, w});
}
//排序原图并进行第一次kruskal
sort(OG.begin(), OG.end(), cmp);
long long ans = kruskal_first();
//cout << ans << endl;
for (int j = 0; j < k; j++) {
c[j] = read();
for (int i = 1; i <= n; i++) {
w = read();
NG.push_back({n+j+1, i, w});
}
}
sort(NG.begin(), NG.end(), cmp);
int MAXK = 1 << k;
//对于乡镇的所有选取状态进行kruskal
for (int s = 1; s < MAXK; s++) ans = min(ans, kruskal(s));
printf("%lld", ans);
return 0;
}