| 等 级 | |
| 排 名 | 17 |
| 经 验 | 20527 |
| 参赛次数 | 3 |
| 文章发表 | 163 |
| 年 龄 | 26 |
| 在职情况 | 学生 |
| 学 校 | |
| 专 业 | 计算机技术 |
自我简介：
读研ing，平时不登录dotcpp
TA的其他文章
| 蓝桥杯算法提高VIP-分分钟的碎碎念 （C++代码） 浏览：610 |
| 蓝桥杯算法提高VIP-分数统计 （C++代码） 浏览：357 |
| 蓝桥杯算法提高VIP-分苹果 （C++代码） 浏览：321 |
你可能喜欢
C语言训练-求素数问题 （C语言代码）浏览：1009 |
人民币问题 （C语言代码）浏览：1461 |
C语言程序设计教程（第三版）课后习题6.4 （C语言代码）浏览：534 |
C语言程序设计教程（第三版）课后习题7.2 （C语言代码）浏览：525 |
人见人爱A+B （C语言代码）浏览：625 |
原题链接：蓝桥杯历届试题-城市建设
解题思路:
首先了解并查集，然后使用克鲁斯卡尔算法找到最小生成树。
参考代码:
#include<cstdio>
#include<algorithm>
#define maxn 10010
#define maxm 100010
#define N 10000000
using namespace std;
int n,m,pre[maxn];
struct edge{
int begin,end,s;
}Edge[maxm+maxn];
int cmp(struct edge x,struct edge y){ return x.s < y.s; }
int mymin(int a,int b){ return a<b?a:b; }
int find(int r)
{
int t = r;
while(pre[r]!=r) r=pre[r];
while(t!=r)
{
int temp=t;
pre[t]=r;
t=pre[temp];
}
return r;
}
int main(void)
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++) scanf("%d%d%d",&Edge[i].begin,&Edge[i].end,&Edge[i].s);
for(int i=m;i<m+n;i++)
{
Edge[i].begin=0; Edge[i].end=i-m+1;
scanf("%d",&Edge[i].s);
if(Edge[i].s==-1) Edge[i].s=-N;
}
sort(Edge,Edge+m+n,cmp);
int sum1=0,sum2=0,cnt=0;
for(int i=0;i<=n;i++) pre[i]=i;
for(int i=0;i<m+n;i++)
{
if(Edge[i].s == -N) continue;
int x = find(Edge[i].begin);
int y = find(Edge[i].end);
if(x!=y)
{
pre[x]=y;
sum1+=Edge[i].s;
}
else if(Edge[i].s<0) sum1+=Edge[i].s;
}
for(int i=1;i<=n;i++) pre[i]=i;
for(int i=0;i<n+m;i++)
{
if(Edge[i].begin==0) continue;
int x = find(Edge[i].begin);
int y = find(Edge[i].end);
if(x!=y)
{
pre[x]=y;
sum2+=Edge[i].s;
}
else if(Edge[i].s<0) sum2+=Edge[i].s;
}
for(int i=1;i<=n;i++) if(pre[i]==i) cnt++;
if(cnt!=1) printf("%d",sum1);
else printf("%d",mymin(sum1,sum2));
return 0;
}0.0分
2 人评分