专栏首页FishCCF 最优灌溉

CCF 最优灌溉

问题描述

  雷雷承包了很多片麦田,为了灌溉这些麦田,雷雷在第一个麦田挖了一口很深的水井,所有的麦田都从这口井来引水灌溉。   为了灌溉,雷雷需要建立一些水渠,以连接水井和麦田,雷雷也可以利用部分麦田作为“中转站”,利用水渠连接不同的麦田,这样只要一片麦田能被灌溉,则与其连接的麦田也能被灌溉。   现在雷雷知道哪些麦田之间可以建设水渠和建设每个水渠所需要的费用(注意不是所有麦田之间都可以建立水渠)。请问灌溉所有麦田最少需要多少费用来修建水渠。

输入格式

  输入的第一行包含两个正整数n, m,分别表示麦田的片数和雷雷可以建立的水渠的数量。麦田使用1, 2, 3, ……依次标号。   接下来m行,每行包含三个整数ai, bi, ci,表示第ai片麦田与第bi片麦田之间可以建立一条水渠,所需要的费用为ci。

输出格式

  输出一行,包含一个整数,表示灌溉所有麦田所需要的最小费用。

样例输入

4 4 1 2 1 2 3 4 2 4 2 3 4 3

样例输出

6

样例说明

  建立以下三条水渠:麦田1与麦田2、麦田2与麦田4、麦田4与麦田3。

评测用例规模与约定

  前20%的评测用例满足:n≤5。   前40%的评测用例满足:n≤20。   前60%的评测用例满足:n≤100。

  所有评测用例都满足:1≤n≤1000,1≤m≤100,000,1≤ci≤10,000。

这个题题意很明确,解法也很明确,就是用最小生成树,使用了prim算法,成功得得到了。。。额。。。40分,原因在于题意说权值是1≤ci≤10,000的,然而其实样例里有等于零的,这个程序里也注释出来了。怎么说呢,我是该吐槽这个题目呢还是该怪自己太教条,按着课本上的来呢。正好也复习了一下prim算法,需要一个辅助的closedge数组。具体还是看程序吧~

#include<iostream>
#define N 1001
#define Max 10001
using namespace std;
int n;
long long int sum; 

typedef struct Edge{
	int v;
	int info;
	struct Edge* next;
}Edge;
Edge head[N];

struct prim{
	int v;
	int lowcost;
}closedge[N];

void AddEdge(int x,int y,int data){
	Edge *tp1,*tp2;
	tp1=new Edge;
	tp2=new Edge;
	tp1->info=tp2->info=data;
	tp1->v=y;
	tp1->next=head[x].next;
	head[x].next=tp1;
	tp2->v=x;
	tp2->next=head[y].next;
	head[y].next=tp2;
}

void prim(){
	//初始化 closedge数组 
	for(int i=0;i<=n;i++)
		closedge[i].lowcost=Max;
	//将第一个点选中 
	//这里比较坑的一点是,距离可能是0,明明数据范围是大于等于1的,所以……一定要注意。。。 
	closedge[1].lowcost=-1;
	//修改和第一个点相关的点的信息 
	for(Edge* i=head[1].next;i;i=i->next){
		int v=i->v;
		closedge[v].lowcost=i->info;
		closedge[v].v=1;
	}
	//从剩下的点开始 
	for(int i=2;i<=n;i++){
		int min=Max,k=0;
		//找到最小的距离的点,选中 
		for(int i=1;i<=n;i++)
			if(closedge[i].lowcost<min && closedge[i].lowcost!=-1){
				min=closedge[i].lowcost;
				k=i;
			}
		closedge[k].lowcost=-1;
		//将求得的边加和 
		sum+=min; 
		//以求得的新点开始修改closedge数组
		for(Edge* j=head[k].next;j;j=j->next){
			int v=j->v;
			if(closedge[v].lowcost>j->info){
				closedge[v].lowcost=j->info;
				closedge[v].v=k;
			}
		}
		
	}
}


int main(){
	int m;
	cin>>n>>m;
	while(m--){
		int x,y,data;
		cin>>x>>y>>data;
		AddEdge(x,y,data);
	}
	
	prim();
	
	cout<<sum;
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 破解sublime 3207(2019.6.3更新)

    最近这几个月都在忙论文的事,基本上没有写博客,今天终于差不多整完了,开始修电脑。前阵子sublime总是有一些稀奇古怪的问题,所以今天就更新一下,主要是解决注册...

    用户1148523
  • 《GPU高性能编程 CUDA实战》(CUDA By Example)读书笔记

    写在最前 这本书是2011年出版的,按照计算机的发展速度来说已经算是上古书籍了,不过由于其简单易懂,仍旧被推荐为入门神书。先上封面: ? 由于书比较...

    用户1148523
  • 蓝桥杯 危险系数

    题意就是求图中两点之间的割点的数目。 不知道被谁指导的说求割点可以用tarjan算法,就用了tarjan算法,但是tarjan算法求的是整个图的割点个数啊,至于...

    用户1148523
  • hihoCoder 1700 相似颜色

            题目链接: http://hihocoder.com/problemset/problem/1700

    Ch_Zaqdt
  • 水题第二弹题解

    改过的标题很具有迷惑性哦! A POJ3414本次代码量最大的一题,思想是搜索,详细解题报告,请见点击打开链接 B巨水,不要被题目迷惑了,连通图的性质最少需要(...

    triplebee
  • Palette状态栏颜色提取,写的不错就分享了

    Palette 说Palette之前先说下前面提到的Pager。ViewPager是什么大家应该都是知道的了,一般ViewPager、xxxTabStrip...

    xiangzhihong
  • QT生成动态链接库.so文件

    首先是新建一个工程,选择C++库,打开后是这样的4 ? 然后输入新建的名称,下一步,记得勾选Qtcore那个(就是默认的那个),否则编译似乎不能通过。因为后面自...

    微风、掠过
  • 指针*和引用&的区别使用

    首先,&不是地址运算符,而是类型标识符的一种,就像*也不是指针运算符一样。 本篇偏向于&运算符。

    看、未来
  • c语言之使用typedef定义类型

    绝命生
  • 快速幂模板

    1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 using namespace ...

    attack

扫码关注云+社区

领取腾讯云代金券