POJ 1751 Highways（最小生成树，kruskal）

题目意思：
给出n个镇，已经修好了m条高速公路，要求在修 剩下的某些高速公路，使得n个镇连通，而费用最少。
本题要点：
1、 先把m条修好的高速公路的距离改为0， 然后用 kruskal 算法模拟;
2、 vis[i][j]表示镇 i和镇j是否已经有高速公路;

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MaxN = 760;
int n, m, tot, ans_cnt;
int fa[MaxN];
bool vis[MaxN][MaxN];	struct Point
{
    int x, y;
}points[MaxN], ans[MaxN];struct rec
{
    int x, y;double z;bool operator<(const rec& rhs) const{
    return z < rhs.z;}
}edge[MaxN * MaxN];int get(int x)
{
    if(x == fa[x]){
    return x;}return fa[x] = get(fa[x]);
}int main()
{
    scanf("%d", &n);for(int i = 1; i <= n; ++i){
    scanf("%d%d", &points[i].x, &points[i].y);}tot = 0;int x, y;scanf("%d", &m);for(int i = 0; i < m; ++i)	// m条边已经建好{
    scanf("%d%d", &x, &y);vis[x][y] = vis[y][x] = true;}double x1, x2, y1, y2;for(int i = 1; i <= n; ++i){
    for(int j = i + 1; j <= n; ++j){
    edge[++tot].x = i, edge[tot].y = j;if(vis[i][j]){
    edge[tot].z = 0;continue;}x1 = points[i].x, x2 = points[j].x, y1 = points[i].y, y2 = points[j].y;edge[tot].z = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));  }}sort(edge + 1, edge + tot + 1);for(int i = 1; i <= n; ++i){
    fa[i] = i;}int u, v;for(int i = 1; i <= tot; ++i){
    u = edge[i].x, v = edge[i].y;x = get(u);y = get(v);if(x == y){
    continue;}fa[x] = y;if(!vis[u][v])	{
    ans[ans_cnt].x = u, ans[ans_cnt++].y = v;}}for(int i = 0; i < ans_cnt; ++i){
    printf("%d %d\n", ans[i].x, ans[i].y);}return 0;
}/* 9 1 5 0 0 3 2 4 5 5 1 0 4 5 2 1 2 5 3 3 1 3 9 7 1 2 *//* 1 6 3 7 4 9 5 7 8 3 */