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

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

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

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

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

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

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 struct edge{

     int u,v,w;

 }e[];

 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=;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=;

     int u,v,i;

     init();

     for(i=;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-)break;

     }

 }

 int main(){

     int i,u,v,w;

     scanf("%d%d",&n,&m);

     for(i=;i<m;++i){

         scanf("%d%d%d",&u,&v,&w);

         e[i]=edge{u,v,w};

     }

     sort(e,e+m,cmp);

     Kruskal();

     printf("%d\n%d\n",ma,ai);

     for(i=;i<ai;++i)

         printf("%d %d\n",e[a[i]].u,e[a[i]].v);

     return ;

 }

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

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=;

 struct edge{

     int u,v,w;

 }e[];

 int f[N];

 int n,m,ans;

 int cmp(edge a,edge b){

     return a.w<b.w;

 }

 void init(){

     for(int i=;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=;

     int u,v,i;

     init();

     for(i=;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[],v[];

     while(scanf("%d",&n),n){

         m=;

         for(i=;i<n-;++i){

             scanf("%s %d",u,&k);

             for(j=;j<k;++j){

                 scanf("%s %d",v,&w);

                 e[m++]={u[]-'A',v[]-'A',w};

             }

         }

         sort(e,e+m,cmp);

         Kruskal();

         printf("%d\n",ans);

     }

     return ;

 }

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

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

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int M=;

 struct edge{

     int u,v,w;

 }e[M];

 int f[];

 int n,m,ans;

 int cmp(edge a,edge b){

     return a.w<b.w;

 }

 void init(){

     for(int i=;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=;

     int u,v,i;

     init();

     for(i=;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=;i<m;++i){

             scanf("%d%d%d",&u,&v,&w);

             e[i]={u,v,w};

         }

         sort(e,e+m,cmp);

         Kruskal();

         printf("%d\n",ans);

     }

     return ;

 }

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

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int M=;

 const int N=;

 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=;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=;

     int u,v,i,cnt=;

     init();

     for(i=;cnt<n-;++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=;i<n;++i){

             scanf("%lf%lf%lf%lf",&a[i],&b[i],&c[i],&r[i]);

         }

         for(m=i=;i<n-;++i){

             for(j=i+;j<n;++j){

                 w=dist(i,j);

                 if(w<) w=;

                 e[m++]={i,j,w};

             }

         }

         sort(e,e+m,cmp);

         Kruskal();

         printf("%.3f\n",ans);

     }

     return ;

 }

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

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int M=;

 const int N=;

 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=;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=;

     int u,v,i,cnt=;

     init();

     for(i=;cnt<n-;++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)==){

         for(i=;i<=n;++i)

             for(j=;j<=n;++j)

             scanf("%d",&g[i][j]);

         memset(vis,,sizeof(vis));

         scanf("%d",&m);

         while(m--){

             scanf("%d%d",&a,&b);

             vis[a][b]=;

         }

         ei=;

         for(i=;i<n;++i){

             for(j=i+;j<=n;++j){

                 if(vis[i][j]) e[ei++]={i,j,};

                 else  e[ei++]={i,j,g[i][j]};

             }

         }

         sort(e,e+ei,cmp);

         Kruskal();

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

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

最新文章

热门文章