UVa10397_Connect the Campus(最小生成樹)(小白書圖論專題)

UVa10397_Connect the Campus(最小生成樹)(小白書圖論專題)

解題報告

題目傳送門

題意：

使得學校網絡互通的最小花費，一些樓的線路已經有了。

思路：

存在的線路當然全都利用那樣花費肯定最小，把存在的線路當成花費0，求最小生成樹

#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
using namespace std;
int n,m,_hash[1110][1110],vis[1100];
double mmap[1110][1110],dis[1100];
struct node {
    double x,y;
} p[1110];
double disc(node p1,node p2) {
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
void prime() {
    for(int i=0; i


Connect the Campus

Input: standard input

Output: standard output

Time Limit: 2 seconds
Many new buildings are under construction on the campus of the University of Waterloo. The university has hired bricklayers, electricians, plumbers, and a computer programmer. A computer programmer? Yes, you have been hired to ensure that each building is
 connected to every other building (directly or indirectly) through the campus network of communication cables.
We will treat each building as a point specified by an x-coordinate and a y-coordinate. Each communication cable connects exactly two buildings, following a straight line between the buildings. Information travels along a cable in both directions. Cables
 can freely cross each other, but they are only connected together at their endpoints (at buildings).
You have been given a campus map which shows the locations of all buildings and existing communication cables. You must not alter the existing cables. Determine where to install new communication cables so that all buildings are connected. Of course, the
 university wants you to minimize the amount of new cable that you use.

Fig: University of Waterloo Campus
 
Input
The input file describes several test case.  The description of each test case is given below:
The first line of each test case contains the number of buildings N (1<=N<=750). The buildings are labeled from 1 to N. The next Nlines give the x and y coordinates
 of the buildings. These coordinates are integers with absolute values at most 10000. No two buildings occupy the same point. After that there is a line containing the number of existing cables M (0 <= M <= 1000) followed byM lines
 describing the existing cables. Each cable is represented by two integers: the building numbers which are directly connected by the cable. There is at most one cable directly connecting each pair of buildings.
Output
For each set of input, output in a single line the total length of the new cables that you plan to use, rounded to two decimal places.
Sample Input
4

103 104

104 100

104 103

100 100

1

4 2
4

103 104
104 100
104 103
100 100
1
4 2
 
Sample Output

4.41

4.41