uva 216 Getting in Line (暴力枚举)
  qvce4elbFrsc 2023年11月02日 35 0


                             uva 216  Getting in Line


Computer networking requires that the computers in the network be linked.

This problem considers a ``linear" network in which the computers are chained together so that each is connected to exactly two others except for the two computers on the ends of the chain which are connected to only one other computer. A picture is shown below. Here the computers are the black dots and their locations in the network are identified by planar coordinates (relative to a coordinate system not shown in the picture).

Distances between linked computers in the network are shown in feet.




For various reasons it is desirable to minimize the length of cable used.

Your problem is to determine how the computers should be connected into such a chain to minimize the total amount of cable needed. In the installation being constructed, the cabling will run beneath the floor, so the amount of cable used to join 2 adjacent computers on the network will be equal to the distance between the computers plus 16 additional feet of cable to connect from the floor to the computers and provide some slack for ease of installation.

The picture below shows the optimal way of connecting the computers shown above, and the total length of cable required for this configuration is (4+16)+ (5+16) + (5.83+16) + (11.18+16) = 90.01 feet.




Input

The input file will consist of a series of data sets. Each data set will begin with a line consisting of a single number indicating the number of computers in a network. Each network has at least 2 and at most 8 computers. A value of 0 for the number of computers indicates the end of input.

After the initial line in a data set specifying the number of computers in a network, each additional line in the data set will give the coordinates of a computer in the network. These coordinates will be integers in the range 0 to 150. No two computers are at identical locations and each computer will be listed once.

Output

The output for each network should include a line which tells the number of the network (as determined by its position in the input data), and one line for each length of cable to be cut to connect each adjacent pair of computers in the network. The final line should be a sentence indicating the total amount of cable used.

In listing the lengths of cable to be cut, traverse the network from one end to the other. (It makes no difference at which end you start.) Use a format similar to the one shown in the sample output, with a line of asterisks separating output for different networks and with distances in feet printed to 2 decimal places.

Sample Input


6 5 19 55 28 38 101 28 62 111 84 43 116 5 11 27 84 99 142 81 88 30 95 38 3 132 73 49 86 72 111 0


Sample Output


********************************************************** Network #1 Cable requirement to connect (5,19) to (55,28) is 66.80 feet. Cable requirement to connect (55,28) to (28,62) is 59.42 feet. Cable requirement to connect (28,62) to (38,101) is 56.26 feet. Cable requirement to connect (38,101) to (43,116) is 31.81 feet. Cable requirement to connect (43,116) to (111,84) is 91.15 feet. Number of feet of cable required is 305.45. ********************************************************** Network #2 Cable requirement to connect (11,27) to (88,30) is 93.06 feet. Cable requirement to connect (88,30) to (95,38) is 26.63 feet. Cable requirement to connect (95,38) to (84,99) is 77.98 feet. Cable requirement to connect (84,99) to (142,81) is 76.73 feet. Number of feet of cable required is 274.40. ********************************************************** Network #3 Cable requirement to connect (132,73) to (72,111) is 87.02 feet. Cable requirement to connect (72,111) to (49,86) is 49.97 feet. Number of feet of cable required is 136.99.





题目大意:给你一些定点,让你以代价最小的边将所有的点连起来。

解题思路:普通欧拉回路。枚举所有排列,记录最小的距离。



#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct comp {
	double x, y;
};
comp com[10];
int no[10], record[10];
double getL(int x1, int y1, int x2, int y2) {
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) + 16;
}
int main() {
	int T, Case = 1;
	while (scanf("%d", &T) == 1, T) {
		for (int i = 0; i < T; i++) {
			scanf("%lf %lf\n", &com[i].x, &com[i].y);
			no[i] = i;
		}
		double min = 0xFFFFFFFF;
		do {
			double sum = 0;
			for (int i = 0; i < T - 1; i++) {
				sum += getL(com[no[i]].x, com[no[i]].y, com[no[i + 1]].x, com[no[i + 1]].y);
			}
			if (sum < min) {
				min = sum;
				for (int i = 0; i < T; i++) {
					record[i] = no[i];
				}
			}
		}
		while (next_permutation(no, no + T));
		printf("**********************************************************\n");  
		printf("Network #%d\n", Case++);  
		for(int i = 0; i < T - 1; i++)  
		{  
			printf("Cable requirement to connect (%.lf,%.lf) to (%.lf,%.lf) is %.2lf feet.\n", com[record[i]].x, com[record[i]].y, com[record[i + 1]].x, com[record[i + 1]].y, getL(com[record[i]].x, com[record[i]].y, com[record[i + 1]].x, com[record[i + 1]].y));  
		}  
		printf("Number of feet of cable required is %.2lf.\n", min);  
	}
	return 0;
}







【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

上一篇: centos 查看版本 下一篇: uva 10970 Big Chocolate
  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
  P3nxyT0LRuwj   2023年11月19日   22   0   0 数据库ide配置文件
  oIa1edJoFmXP   2023年11月22日   24   0   0 ide数据List
  YKMEHzdP8aoh   2023年12月11日   61   0   0 DNSidePod
  3n45YYmVLV9P   2023年11月13日   19   0   0 ico#includeLine
  YKMEHzdP8aoh   2023年11月24日   36   0   0 ide重定向Rust
qvce4elbFrsc