简答题
偏难
#21997
T2道路修复
T2道路修复



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre>
这道题暂未补解析。