题意：

在这些小岛中建设最小花费的桥，但是一座桥的距离必须在10 -- 1000之间。

思路：

用最小生成树解决吧，就那两个算法。

代码：

prim

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define N 105#define inf 0x3f3f3f3fint n,i,j,x[N],y[N];double map[N][N];bool vis[N];//标记是否已经放入最小生成树的那个集合里了double low[N];//记录不在已经加入最小生成树的这个集合里的元素到这个 集合的最小距离double dis(int i,int j){    return sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}void init(){    for(i=1;i<=n;++i)        cin>>x[i]>>y[i];    for(i=1;i<=n;++i)        for(j=1;j<=n;++j)        {            map[i][j]=dis(i,j);            if(map[i][j]>1000||map[i][j]<10)            {                map[i][j]=inf;            }        }}void prim(){    double sum=0;    memset(vis,0,sizeof(vis));    int pos=1;//从1开始    for(i=1;i<=n;++i)//第一次给low赋值    {        low[i]=map[1][i];    }    vis[1]=1;    //已经找到一个点1，再找n-1个    for(i=1;i
          
           low[j])//找下一个点到这个集合的最小值            {                min=low[j];//记下这个最小值                pos=j;//记下这个点            }        }        if(min==inf)        {            cout<<"oh!"<
           
            map[pos][j]) { low[j]=map[pos][j]; } } } printf("%.1lf\n",sum*100);}int main(){ int t; cin>>t; while(t--) { cin>>n; init(); prim(); } return 0;}
           
          
         
        
       
      

kruskal

#include
      
       #include
       
        #include
        
         using namespace std;struct Island{    int x,y;};struct node {    int u,v;    double w;};Island arr[220];node  edge[20000];int per[220];int n;bool cmp(node a,node b){    return a.w
         
          =10&&join(edge[i].u,edge[i].v))//如果两个岛的距离不符合要求就会把join(edge[i].u,edge[i].v）短路            {                sum+=edge[i].w;            }        }        int cnt=0;        bool flag=0;        for(i=1;i<=n;++i)//短路了就不会执行了，也就不会连接了，就只需要判断根节点的个数        {            if(i==per[i]) cnt++;            if(cnt>1) //不等于1就还有元素（小岛）没连起来，不满足题意            {                flag=1;                break;            }        }        if(flag) printf("oh!\n");        else            printf("%.1lf\n",sum*100);    }    return 0;}