最小生成树练习1（克鲁斯卡尔算法Kruskal）

今天刷一下水题练手入门，明天继续。

poj1861 Network（最小生成树）新手入门题。

题意：输出连接方案中最长的单根网线长度（必须使这个值是所有方案中最小的），然后输出方案。

题解：本题没有直接求生成树，但如果连接n个集线器的方案多于n-1条边，那么必存在回路，因此去掉某些边剩下的边和所有顶点构成一个生成树。对于一个图的最小生成树来说，它的最大边满足所有生成树的最大边里最小，正和题意。

吐槽：题目样例是错的。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1001;
struct edge{
    int u,v,w;
}e[15001];
int f[N],a[N],ai;
int n,m,ma;
int cmp(edge a,edge b){
    return a.w<b.w;
}
void init(){
    for(int i=1;i<=n;++i)
        f[i]=i;
}
int fin(int x){
    if(x!=f[x])f[x]=fin(f[x]);
    return f[x];
}
void Kruskal(){
    ma=ai=0;
    int u,v,i;
    init();
    for(i=0;i<m;++i){
        u=e[i].u;
        v=e[i].v;
        if((u=fin(u))!=(v=fin(v))){
            f[u]=v;
            a[ai++]=i;
            ma=max(e[i].w,ma);
        }
        if(ai>=n-1)break;
    }
}
int main(){
    int i,u,v,w;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;++i){
        scanf("%d%d%d",&u,&v,&w);
        e[i]=edge{u,v,w};
    }
    sort(e,e+m,cmp);
    Kruskal();
    printf("%d
%d
",ma,ai);
    for(i=0;i<ai;++i)
        printf("%d %d
",e[a[i]].u,e[a[i]].v);
    return 0;
}

poj1251 Jungle Roads（最小生成树）水题。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=27;
struct edge{
    int u,v,w;
}e[75];
int f[N];
int n,m,ans;
int cmp(edge a,edge b){
    return a.w<b.w;
}
void init(){
    for(int i=0;i<n;++i)
        f[i]=i;
}
int fin(int x){
    if(x!=f[x])f[x]=fin(f[x]);
    return f[x];
}
void Kruskal(){
    ans=0;
    int u,v,i;
    init();
    for(i=0;i<m;++i){
        u=e[i].u;
        v=e[i].v;
        if((u=fin(u))!=(v=fin(v))){
            f[u]=v;
            ans+=e[i].w;
        }
    }
}
int main(){
    int i,j,w,k;
    char u[3],v[3];
    while(scanf("%d",&n),n){
        m=0;
        for(i=0;i<n-1;++i){
            scanf("%s %d",u,&k);
            for(j=0;j<k;++j){
                scanf("%s %d",v,&w);
                e[m++]={u[0]-'A',v[0]-'A',w};
            }
        }
        sort(e,e+m,cmp);
        Kruskal();
        printf("%d
",ans);
    }
    return 0;
}

poj1287 Networking（最小生成树）水题。

用prim要注意两个地点之间的线路可能多条，即有重边。我这里练的是Kruskal，题目没给边数，但知道点数最多50，则边数最多50*49/2=1225条，有重边，开大点数组就行，因为数据弱，随便开个1500都过了，醉。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1500;
struct edge{
    int u,v,w;
}e[M];
int f[50];
int n,m,ans;
int cmp(edge a,edge b){
    return a.w<b.w;
}
void init(){
    for(int i=1;i<=n;++i)
        f[i]=i;
}
int fin(int x){
    if(x!=f[x])f[x]=fin(f[x]);
    return f[x];
}
void Kruskal(){
    ans=0;
    int u,v,i;
    init();
    for(i=0;i<m;++i){
        u=e[i].u;
        v=e[i].v;
        if((u=fin(u))!=(v=fin(v))){
            f[u]=v;
            ans+=e[i].w;
        }
    }
}
int main(){
    int i,u,v,w;
    while(scanf("%d",&n),n){
        scanf("%d",&m);
        for(i=0;i<m;++i){
            scanf("%d%d%d",&u,&v,&w);
            e[i]={u,v,w};
        }
        sort(e,e+m,cmp);
        Kruskal();
        printf("%d
",ans);
    }
    return 0;
}

poj2031 Building a Space Station（最小生成树）题目看老久，其实挺水…空间站存在一些球形单间，如果单间之间接触，重叠或用走廊连接则连通。给出单间坐标和半径，求要使得所有单间相连通的走廊总长度的最小值。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int M=5000;
const int N=100;
struct edge{
    int u,v;
    double w;
}e[M];
double a[N],b[N],c[N],r[N];
int f[N];
int n,m;
double ans;
int cmp(edge a,edge b){
    return a.w<b.w;
}
double dist(int i,int j){
    return sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j])+(c[i]-c[j])*(c[i]-c[j]))-r[i]-r[j];
}
void init(){
    for(int i=0;i<n;++i) f[i]=i;
}
int fin(int x){
    if(x!=f[x])f[x]=fin(f[x]);
    return f[x];
}
void Kruskal(){
    ans=0;
    int u,v,i,cnt=0;
    init();
    for(i=0;cnt<n-1;++i){
        u=e[i].u;
        v=e[i].v;
        if((u=fin(u))!=(v=fin(v))){
            f[u]=v;
            ans+=e[i].w;
            cnt++;
        }
    }
}
int main(){
    int i,j;
    double w;
    while(scanf("%d",&n),n){
        for(i=0;i<n;++i){
            scanf("%lf%lf%lf%lf",&a[i],&b[i],&c[i],&r[i]);
        }
        for(m=i=0;i<n-1;++i){
            for(j=i+1;j<n;++j){
                w=dist(i,j);
                if(w<0) w=0;
                e[m++]={i,j,w};
            }
        }
        sort(e,e+m,cmp);
        Kruskal();
        printf("%.3f
",ans);
    }
    return 0;
}

poj2421 Constructing Roads（最小生成树）水题。有些点已经连边，进行标记，加边时将其边赋值为0即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=5000;
const int N=101;
struct edge{
    int u,v,w;
}e[M];
int f[N];
int g[N][N],vis[N][N];
int n,ans;
int cmp(edge a,edge b){
    return a.w<b.w;
}
void init(){
    for(int i=1;i<=n;++i) f[i]=i;
}
int fin(int x){
    if(x!=f[x])f[x]=fin(f[x]);
    return f[x];
}
void Kruskal(){
    ans=0;
    int u,v,i,cnt=0;
    init();
    for(i=0;cnt<n-1;++i){
        u=e[i].u;
        v=e[i].v;
        if((u=fin(u))!=(v=fin(v))){
            f[u]=v;
            ans+=e[i].w;
            cnt++;
        }
    }
}
int main(){
    int i,j,a,b,ei,m;
    while(scanf("%d",&n)==1){
        for(i=1;i<=n;++i)
            for(j=1;j<=n;++j)
            scanf("%d",&g[i][j]);
        memset(vis,0,sizeof(vis));
        scanf("%d",&m);
        while(m--){
            scanf("%d%d",&a,&b);
            vis[a][b]=1;
        }
        ei=0;
        for(i=1;i<n;++i){
            for(j=i+1;j<=n;++j){
                if(vis[i][j]) e[ei++]={i,j,0};
                else  e[ei++]={i,j,g[i][j]};
            }
        }
        sort(e,e+ei,cmp);
        Kruskal();
        printf("%d
",ans);
    }
    return 0;
}