目录
一、第一代代码
这道题我起先只写了一个60分代码，代码如下：
#include<bits/stdc++.h> using namespace std; struct line_information { int need; int from; int to; int value; }line[10001]; int f[2001]; int n, m, il = 0; bool cmpl(line_information a, line_information b) { return a.value < b.value; } int find(int i) { if(f[i] != i) f[i] = find(f[i]); return f[i]; } int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) f[i] = i; for(int i = 1; i <= m; i++) { int p, u, v, m; scanf("%d %d %d %d", &p, &u, &v, &m); il++; line[il].need = p; line[il].from = u; line[il].to = v; line[il].value= m; } sort(line+1, line+il+1, cmpl); int ans = 0; for(int i = 1; i <= il; i++) { // printf("%d ", line[i].value); if(line[i].need == 1) { f[find(line[i].from)] = find(line[i].to); ans += line[i].value; } if(find(line[i].from) != find(line[i].to)) { f[find(line[i].from)] = find(line[i].to); ans += line[i].value; } } printf("%d", ans); return 0; } 二、第二代代码
然后，我把线路必选的判断放到了输入中，于是就100分了，代码如下：
#include<bits/stdc++.h> using namespace std; struct line_information { int need; int from; int to; int value; }line[10001]; int f[2001]; int n, m, il = 0; bool cmpl(line_information a, line_information b) { return a.value < b.value; } int find(int i) { if(f[i] != i) f[i] = find(f[i]); return f[i]; } int main() { int ans = 0; scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) f[i] = i; for(int i = 1; i <= m; i++) { int p, u, v, m; scanf("%d %d %d %d", &p, &u, &v, &m); if(p == 1) { f[find(u)] = find(v); ans += m; } il++; line[il].need = p; line[il].from = u; line[il].to = v; line[il].value= m; } sort(line+1, line+il+1, cmpl); for(int i = 1; i <= il; i++) { // printf("%d ", line[i].value); if(find(line[i].from) != find(line[i].to)) { f[find(line[i].from)] = find(line[i].to); ans += line[i].value; } } printf("%d", ans); return 0; } 三、我的疑问
请问大佬们，这是为什么呢？
今天的文章 最小生成树，联络员（liaison）题解与疑问分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/100522.html