注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

kruskal  

2008-04-12 09:44:21|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

给大家一个kruskal算法

#include <fstream>
#include <iostream>
using namespace std;
struct myline{
       int a,b;
};
int ok[100];
int father[100];
int inimap();
int n,d;
int map[100][100];
myline lines[10000];
int inimap()
{
    ifstream fin("in.txt");
    fin >>n;
    d=0;
    int i,j,k,l=0,min,minida,minidb;
    for (i=0;i<n;i++)
    {
        for (j=0;j<n;j++)
        {
            fin >>map[i][j];
            if (i<j && map[i][j]>0)
            {
                    d++;
                    lines[l].a=i;
                    lines[l].b=j;
                    l++;
            }
        }
    }
    myline tmp;
    for (i=0;i<d;i++)
    {
        min=2000000;
        for (j=i;j<d;j++)
        {
            if (map[lines[j].a][lines[j].b]<min)
            {
               min=map[lines[j].a][lines[j].b];
               minida=j;
            }
        }
        tmp=lines[i];
        lines[i]=lines[minida];
        lines[minida]=tmp;
    }
    for (i=0;i<d;i++){cout <<map[lines[i].a][lines[i].b]<<' ';}
    cout <<endl;
    for (i=0;i<n;i++)father[i]=-1;
    return 0;
}
int find(int j)
{
    if (father[j]==-1)return j;
    int i;
    i=find(father[j]);father[j]=i;return i;
}
int together(int j,int k)
{
    if (find(j)==find(k))return 1;
    return 0;
}
int thesame(int j,int k)
{
    father[find(j)]=find(k);
    return 0;
}
int main()
{
    inimap();
    int i,j,k,cost=0;
    for (i=0;i<d;i++)
    {
        j=lines[i].a;k=lines[i].b;
        if (!together(j,k))
        {
           thesame(j,k);cost+=map[j][k];
        }
    }
    cout <<cost;system("pause");
    return 0;
}

  评论这张
 
阅读(352)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017