本文共 949 字，大约阅读时间需要 3 分钟。

题意：给你n个点和一些集合，在集合中的点是相互联通的，现在需要修建一些路使得n个点相互联通，其中每条路你可以修建也可以买，如果修建的话花费是两个点之间的欧几里得距离，其中点是在二维坐标中。每个点的位置都给出了，如果要修建的这条边在某个集合中，你也可以选择把这个集合买下来，每个集合的花费也给出了。

思路：先根据每个点的最坐标求出两点之间的欧几里得距离，再在每两点之间修建道路，先不买任何集合求出此时最小的花费，此时就是求图的最小生成树，然后在二进制枚举，因为已经告诉你集合的个数不超过8个，所以可以进行二进制枚举，看买那些边，如果要是买下其中一些集合的话，使用并查集把这些点都加到一起。然后在根据把边加到一起之后在求最小生成树，这时求最小生成树时就爱直接根据不买任何集合时的最小生成树求，因为求最小的花费所使用的肯定是最小生成树里的一些边。

#include 
   
    using namespace  std;const int maxn=1e6+50;int n,m;int cnt;int c;struct Point{    int x,y;} p[maxn];struct Node{    int x,y,w;} node[maxn],mst[maxn];struct Team{    int val,num;    int v[maxn];} sub[10];int fa[maxn];void Init(){    for(int i=0; i<=n; i++)        fa[i]=i;}long long int Dig(int x,int y){    long long   int xx=p[x].x-p[y].x;    long long  int yy=p[x].y-p[y].y;    return (long long int)(xx*xx+yy*yy);}int Find_x(int x){    return fa[x]=(x==fa[x]?x:Find_x(fa[x]));}long long int solve(){    long long int res=0;    for(int i=0; i
    
     0) cout<
    
   

转载地址：http://mfgsi.baihongyu.com/