题意：给出n个点的坐标,要把n个点连通，使得总距离最小，但是有m对点已经连接，输入m，和m组a和b，表示a和b两点已经连接。
思路：两种做法，（1）用prim算法时，输入a，b，，令mp[a][b]=0，然后进行一遍prim（2）Kruskal算法+并查集
代码：//prim写法#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i–)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef long long ll;using namespace std;#define INF 0x3f3f3f3f#define mod 1000000009const int maxn = 1005;const int MAXN = 2005;const int MAXM = 200010;const int N = 1005;struct Node{double x,y;}node[maxn];int n,m;double mp[maxn][maxn];double dist[maxn];bool vis[maxn];double Dis(Node n1,Node n2){return sqrt((n1.x-n2.x)*(n1.x-n2.x)+(n1.y-n2.y)*(n1.y-n2.y));}double prim(){int i,j,now;double mi;mem(vis,false);mem(dist,INF);for (i=1;i<=n;i++)dist[i]=mp[1][i];dist[1]=0;vis[1]=true;for (i=1;i<=n;i++){now=-1;mi=INF;for (j=1;j<=n;j++){if (!vis[j]&&mi>dist[j]){now=j;mi=dist[j];}}if (now==-1) break;vis[now]=true;for (j=1;j<=n;j++){if (!vis[j]&&dist[j]>mp[now][j])dist[j]=mp[now][j];}}double ans=0;for (i=1;i<=n;i++)ans+=dist[i];return ans;}int main(){#ifndef ONLINE_JUDGEfreopen("C:/Users/lyf/Desktop/IN.txt","r",stdin);#endifint i,j,u,v;while (~sf(n)){for (i=1;i<=n;i++)scanf("%lf%lf",&node[i].x,&node[i].y);for (i=1;i<=n;i++){for (j=1;j<=n;j++)if (i==j) mp[i][j]=0;else mp[i][j]=Dis(node[i],node[j]);}sf(m);for (i=0;i<m;i++) //在同一个联通块的距离直接赋为0{sff(u,v);mp[u][v]=mp[v][u]=0;}printf("%.2f\n",prim());}return 0;}//Kruskal+并查集写法#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <map>#include <stack>#include <vector>#include <set>#include <queue>#pragma comment (linker,"/STACK:102400000,102400000")#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i–)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i–)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n)scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pfprintf#define DBGpf("Hi\n")typedef long long ll;using namespace std;#define INF 0x3f3f3f3f#define mod 1000000009const int maxn = 1005;const int MAXN = 1000000;const int MAXM = 200010;const int N = 1005;struct Node{double x,y;}node[maxn];struct Edge{int u,v;double len;}edge[MAXN];int n,m,cnt;int father[maxn];int cmp(Edge e1,Edge e2){return e1.len<e2.len;}void init(){cnt=0;for (int i=0;i<=n;i++)father[i]=i;}double Dis(Node n1,Node n2){return sqrt((n1.x-n2.x)*(n1.x-n2.x)+(n1.y-n2.y)*(n1.y-n2.y));}int find_father(int x){if (x!=father[x])father[x]=find_father(father[x]);return father[x];}double Kruskal(){int i,j;double ans=0;sort(edge,edge+cnt,cmp);for (i=0;i<cnt;i++){int fu=find_father(edge[i].u);int fv=find_father(edge[i].v);if (fu!=fv){ans+=edge[i].len;father[fu]=fv;}}return ans;}int main(){#ifndef ONLINE_JUDGEfreopen("C:/Users/lyf/Desktop/IN.txt","r",stdin);#endifint i,j,u,v;while (~sf(n)){init();for (i=1;i<=n;i++)scanf("%lf%lf",&node[i].x,&node[i].y);for (i=1;i<n;i++){for (j=i+1;j<=n;j++){if (i==j) continue;else{double x=Dis(node[i],node[j]);edge[cnt].u=i;edge[cnt].v=j;edge[cnt++].len=x;}}}sf(m);for (i=1;i<=m;i++){sff(u,v);int fu=find_father(u);int fv=find_father(v);if (fu!=fv)father[fu]=fv;}printf("%.2f\n",Kruskal());}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
人生的失败往往是在关键时刻少了坚持。
