浩歌道路修复找虫
2026-01-02 16:11:25
发布于：广东
3阅读
0回复
0点赞
1) g 越界：vector<node> g(m); 却用 g[1..m]
vector<node> g(m);
for (ll i=1;i<=m;i++){
cin >> g[i].u >> g[i].v >> g[i].w; // g[m] 越界，g[0] 没读
}
g的合法下标是0..m-1，你却访问到m。sort(g.begin(), g.end())还会把 没初始化的 g[0] 也拿去排，结果完全不可控。
✅修法：要么开 m+1 并从 1 开始用；要么统一用 0-based。
2) 读乡镇的 少读了一个：
for(ll j=1,x;j<n;j++){ // 只读了 n-1 个
cin >> x;
e.push_back({n+i,j,x,i});
}
- 输入每个乡镇是
n+1个数：。 - 你只读了 ， 留在输入流里，后面所有读入都会错位。
✅修法：j<=n
3) 枚举子集时只处理了 e 的前 k 条边：严重逻辑错误
for(ll i=1;i<=k;i++){
ll u=e[i].u, v=e[i].v, ...
}
e里边数大概是(n-1) + k*n，你只跑了k条边，几乎啥都没连起来。- 正确应该遍历
e.size()。
✅修法：for (size_t i=0;i<e.size();i++)
4) ans 从来没有被更新过
你只在子集循环里算了 res，但最后没有：
ans = min(ans, res);
所以输出永远是 LLONG_MAX（或者溢出后的怪数）。
✅修法：在每个子集结束后，先判断是否让原有 n 城市连通，连通再 ans=min(ans,res)。
5) 连接性检查缺失（而且你 DSU 包含了未选择的乡镇节点）
题目只要求 原来的 1..n 城市两两连通，不要求未选乡镇节点也连通。
你现在：
- DSU 初始化到
n+k； - 但没检查
1..n是否同一连通块； - 甚至你把“未选择的乡镇节点”也放在图里，按 MST 思路会引入概念混乱（虽然你也没真做完 MST）。
✅正确检查方式（子集 p 做完并选边后）：
int rt = find(1);
bool ok = true;
for (int i=2;i<=n;i++) if (find(i)!=rt) ok=false;
if (ok) ans=min(ans,res);
这里空空如也
有帮助，赞一个