Highways「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

Description

Input

Output

Sample Input

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

Sample Output

1 6
3 7
4 9
5 7
8 3

code:

prim算法

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<sstream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int maxn=755;
const int INF=1000000;
double graph[maxn][maxn];
double lowcost[maxn];/*lowcost表示每个点的最小花费;*/
int closet[maxn];/*closet表示最小花费对应相连的点*/
int visited[maxn];/*visited区分两个集合*/
int n;/*n个点*/

struct dot{
    double x,y;
}a[maxn];

double f(dot p,dot q){
    return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
}

void createGraph(){
    memset(graph,0,sizeof(graph));
    memset(lowcost,0,sizeof(lowcost));
    memset(closet,0,sizeof(closet));
    memset(visited,0,sizeof(visited));
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++){
        if(i==j) graph[i][j]=INF;
        else graph[i][j]=graph[j][i]=f(a[i],a[j]);
    }
}

void prim(){
    visited[0]=1;/*选中第一个点*/
    for(int i=0;i<n;i++){
        lowcost[i]=graph[i][0];/*每个点与第一个点的权值*/
        closet[i]=0;/*与i点相连的是第一个点*/
    }
    for(int i=1;i<n;i++){  /*剩下n-1个点*/
        int k=0;
        double minn=lowcost[0];
        for(int j=0;j<n;j++){
            if(!visited[j] && lowcost[j]<minn){
                minn=lowcost[j];
                k=j;
            }
        }
        if(graph[k][closet[k]]!=0) printf("%d %d\n",k+1,closet[k]+1);
        visited[k]=1;
        for(int t=0;t<n;t++){  /*松弛操作*/
            if(!visited[t] && lowcost[t]>graph[t][k]){
                lowcost[t]=graph[t][k];
                closet[t]=k;
            }
        }
    }
}

int main()
{
 //   freopen("input.txt","r",stdin);
    int m;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    createGraph();
    scanf("%d",&m);
    int b,c;
    while(m--){
        scanf("%d%d",&b,&c);
        graph[b-1][c-1]=graph[c-1][b-1]=0;
    }
    prim();
}

Kruskal算法：注意要用G++提交

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<sstream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
const int MAXN = 755; /*结点数目上限*/
int pa[MAXN];    /*pa[x]表示x的父节点*/
int rank[MAXN];    /*rank[x]是x的高度的一个上界*/
int flag;
struct node{
    int x,y;
    double w;
}edge[MAXN*MAXN];

struct dot{
    double x,y;
}a[MAXN];

bool cmp(node p,node q){
    return p.w<q.w;
}

double f(dot p,dot q){
    return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
}

/*创建一个单元集*/
void make_set(int x)
{
    pa[x] = x;
    rank[x] = 0;
}

/*带路径压缩的查找*/
int find_set(int x)
{
    if(x != pa[x])
        pa[x] = find_set(pa[x]);
    return pa[x];
}

/*按秩合并x，y所在的集合*/
void union_set(int xx, int yy,double w)
{
    int x = find_set(xx);
    int y = find_set(yy);
    if(x == y)return ;
    if(rank[x] > rank[y])/*让rank比较高的作为父结点*/
    {
        pa[y] = x;
    }
    else
    {
        pa[x] = y;
        if(rank[x] == rank[y])
            rank[y]++;
    }
    if(w!=0){
        printf("%d %d\n",xx,yy);
        flag=1;
    }
}

int main()
{
   // freopen("input.txt","r",stdin);
    int n,m;
    scanf("%d",&n);
    for(int i=0;i<MAXN;i++)
        make_set(i);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    int k=0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            edge[k].x=i;
            edge[k].y=j;
            edge[k].w=f(a[i],a[j]);
            k++;
        }
    }
    scanf("%d",&m);
    int b,c;
    while(m--){
        scanf("%d%d",&b,&c);
        union_set(b,c,0);
    }
    sort(edge,edge+k,cmp);
    flag=0;
    for(int i=0;i<k;i++){
        union_set(edge[i].x,edge[i].y,edge[i].w);
    }
    if(!flag) printf("\n");
}