文档章节

复试训练——图论—— 最小生成树(MST)

wudangt
 wudangt
发布于 2017/02/06 21:12
字数 923
阅读 11
收藏 0

题目1017:还是畅通工程

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:6104

解决:3034

题目描述:

    某省调查乡村交通状况,得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连,只要能间接通过公路可达即可),并要求铺设的公路总长度为最小。请计算最小的公路总长度。

输入:

    测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离,每行给出一对正整数,分别是两个村庄的编号,以及此两村庄间的距离。为简单起见,村庄从1到N编号。
    当N为0时,输入结束,该用例不被处理。

输出:

    对每个测试用例,在1行里输出最小的公路总长度。

样例输入:

3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0

样例输出:

3
5

来源:

2006年浙江大学计算机及软件工程研究生机试真题

代码:

#include <stdio.h>
#include <algorithm>
using namespace std;
#define N 101
int Tree[N];
int findRoot(int x){
	if(Tree[x]==-1) return x;
	else{
		int tmp=findRoot(Tree[x]);
			Tree[x]=tmp;
			return tmp;
	}
}
struct Edge{
	int a,b;
	int cost;
	bool operator < (const Edge &A) const{
		return cost<A.cost;
	}
}edge[6000];
int main(){
	int n;
	while(scanf("%d",&n)!=EOF&&n!=0){
		int i;
		for(i=1;i<=n*(n-1)/2;i++){
			scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].cost);
		}
		sort(edge+1,edge+1+n*(n-1)/2);
		for(i=1;i<=n;i++){
			Tree[i]=-1;
		}
		int ans=0;
		for(i=1;i<n*(n-1)/2;i++){
			int a=findRoot(edge[i].a);
			int b=findRoot(edge[i].b);
			if(a!=b){
				Tree[a]=b;
				ans+=edge[i].cost;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

题目1144:Freckles

时间限制:1 秒

内存限制:32 兆

特殊判题:

提交:2200

解决:1057

题目描述:

    In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad's back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley's engagement falls through. 
    Consider Dick's back to be a plane with freckles at various (x,y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink used. Richie connects the dots by drawing straight lines between pairs, possibly lifting the pen between lines. When Richie is done there must be a sequence of connected lines from any freckle to any other freckle. 

输入:

    The first line contains 0 < n <= 100, the number of freckles on Dick's back. For each freckle, a line follows; each following line contains two real numbers indicating the (x,y) coordinates of the freckle.

输出:

    Your program prints a single real number to two decimal places: the minimum total length of ink lines that can connect all the freckles.

样例输入:

3
1.0 1.0
2.0 2.0
2.0 4.0

样例输出:

3.41

来源:

2009年北京大学计算机研究生机试真题

代码:

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define N 101
int Tree[N];
int findRoot(int x){
	if(Tree[x]==-1){
		return x;
	}else{
	int tmp=findRoot(Tree[x]);
		Tree[x]=tmp;
		return tmp;
	}
}
struct Edge{
	int a,b;
	double cost;
	bool operator <(const  Edge &A)const{
		return cost<A.cost;
	}
}edge[6000];
struct Point {
	double x,y;
	double getDistance(Point A){
		double tmp=(x-A.x)*(x-A.x)+(y-A.y)*(y-A.y);
		return sqrt(tmp);
	}
}list[101];
int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		int i;
		for(i=1;i<=n;i++){
			scanf("%lf%lf",&list[i].x,&list[i].y);
		}
		int size=0;
		for(i=1;i<=n;i++){
			int j;
			for(j=i+1;j<=n;j++){
				edge[size].a=i;
				edge[size].b=j;
				edge[size].cost=list[i].getDistance(list[j]);
				size++;
			}
		}
		sort(edge,edge+size);
		for(i=1;i<=n;i++){
			Tree[i]=-1;
		}
		double ans=0;
		for(i=0;i<size;i++){
			int a=findRoot(edge[i].a);
			int b=findRoot(edge[i].b);
			if(a!=b){
				Tree[a]=b;
				ans+=edge[i].cost;
			}
		}
		printf("%.2lf\n",ans);
	}
	return 0;
}

 

© 著作权归作者所有

wudangt
粉丝 0
博文 46
码字总数 23847
作品 0
黄浦
其他
私信 提问
POJ 1258 Agri-Net(Prim求最小生成树)

0 4 9 214 0 8 179 8 0 1621 17 16 0 28 Source Sample Output [Submit] [Go Back] [Status] [Discuss] 最小生成树——Minimum Spanning Tree,是图论中比较重要的模型,通常用于解决实际生活......

fire_to_cheat_
2018/03/07
0
0
考研复试系列——第六节 最小生成树

考研复试系列——第六节 最小生成树 前言 基础知识 //Kruskal算法基本原理:/** 1. 初始时所有节点都属于孤立的集合* 2. 按照边的权重的递增顺序遍历,若遍历到的边的两个节点分别属于不同的...

cassiepython
2017/03/04
0
0
Codeforces 892E - Envy 【最小生成树】

E. Envy time limit per test 2 seconds memory limit per test 256 megabytes For a connected undirected weighted graph G, MST (minimumspanning tree) is a subgraph of G that contain......

my_sunshine26
2017/12/19
0
0
CCNP笔记——MST上

CCNP笔记--MSTP上 第一次看CCNP学习指南时,对书中描述MST的部分简直一头雾水,有种受挫的感觉。后来通过实验并结合书中的内容才对MST有了初步的了解。下面通过实验说明自己对MSTP的认识: ...

taolinba213
2016/07/18
0
0
SDUT-图结构练习——最小生成树

图结构练习——最小生成树 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 有n个城市,其中有些城市之间可以修建公路,修建不同的公路费用是不同的。现在我们想知道,最少花...

wzy_2017
2017/06/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
今天
5
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
9
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
12
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
昨天
11
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部