POJ 2349 Arctic Network

題意：也是求最小生成樹，不過在n個點當中可以有s個點已經相連。

用krusical做。記錄每次加的邊數，當連通的邊數有n-s便跳出。

 #include<iostream>   
#include<cstdio>   
#include<cmath>   
#include<cstring>   
#include<algorithm>   
using namespace std;  
int n,s,f[1010];  
struct node  
{  
    int x,y;  
    double s;  
}e[250010];  
bool cmp(node s, node v)  
{  
    return s.s<v.s;  
}  
int find(int x)  
{  
    if (x==f[x]) return x;  
    f[x]=find(f[x]);  
    return f[x];  
}  
void krusical(int p)  
{  
    int i,t=0;  
    for (i=0; i<p; i++)  
    {  
        int x=find(e[i].x);  
        int y=find(e[i].y);  
        if (x!=y)  
        {  
            f[y]=f[x];  
            t++;  
        }  
        if (t==n-s) break;  
    }  
    printf("%.2f\n",e[i].s);  
}  
int main ()  
{  
    int t,i,j;  
    cin>>t;  
    while(t--)  
    {  
        int zb[510][2],p=0;  
        cin>>s>>n;  
        for (i=1; i<=n; i++)  
        {  
            f[i]=i;  
            scanf("%d%d",&zb[i][0],&zb[i][1]);  
        }  
        for (i=1; i<n; i++)  
            for (j=i+1; j<=n; j++)  
            {  
                e[p].x=i;  
                e[p].y=j;  
                e[p].s=sqrt((zb[i][0]-zb[j][0])*(zb[i][0]-zb[j][0])+(zb[i][1]-zb[j][1])*(zb[i][1]-zb[j][1]));  
                p++;  
            }  
        sort(e,e+p,cmp);  
        krusical(p);  
    }  
    return 0;  
}  

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int n,s,f[1010];
struct node
{
    int x,y;
    double s;
}e[250010];
bool cmp(node s, node v)
{
    return s.s<v.s;
}
int find(int x)
{
    if (x==f[x]) return x;
    f[x]=find(f[x]);
    return f[x];
}
void krusical(int p)
{
    int i,t=0;
    for (i=0; i<p; i++)
    {
        int x=find(e[i].x);
        int y=find(e[i].y);
        if (x!=y)
        {
            f[y]=f[x];
            t++;
        }
        if (t==n-s) break;
    }
    printf("%.2f\n",e[i].s);
}
int main ()
{
    int t,i,j;
    cin>>t;
    while(t--)
    {
        int zb[510][2],p=0;
        cin>>s>>n;
        for (i=1; i<=n; i++)
        {
            f[i]=i;
            scanf("%d%d",&zb[i][0],&zb[i][1]);
        }
        for (i=1; i<n; i++)
            for (j=i+1; j<=n; j++)
            {
                e[p].x=i;
                e[p].y=j;
                e[p].s=sqrt((zb[i][0]-zb[j][0])*(zb[i][0]-zb[j][0])+(zb[i][1]-zb[j][1])*(zb[i][1]-zb[j][1]));
                p++;
            }
        sort(e,e+p,cmp);
        krusical(p);
    }
    return 0;
}