巢穴

about:blank

P1258 By kruskal

kruskal..
/*
Kruskal
*/
#include <iostream>
using namespace std;

const int MAXN=101;
const int INF=0x7fffffff;
int n;
struct node
{
       int x,y;
       int value;
};
node edge[MAXN*MAXN+1];
bool hash[MAXN];
int dist[MAXN];
int father[MAXN];
int len;
void sort(int l,int r)
{
     int ll=l,rr=r,mid=edge[(l+r)/2].value;
     while(ll<=rr)
     {
      while (edge[ll].value<mid) ll++;
      while (edge[rr].value>mid) rr--;
      if (ll<=rr)
      {
       swap(edge[ll],edge[rr]);
       ll++;
       rr--;
      }
     }
     if (ll<r) sort(ll,r);
     if (rr>l) sort(l,rr);
}
int getFather(int x)
{
    if (x==father[x]) return x;
    father[x]=getFather(father[x]);
    x=father[x];
    return x;
}
void kruskal()
{
     sort(1,len);
     for (int i=0;i<n;i++)
         father[i]=i;
     int ans=0;
     for (int i=1;i<=len;i++)
     {
         int fx=getFather(edge[i].x);
         int fy=getFather(edge[i].y);
         if (fx!=fy)
         {
          ans+=edge[i].value;
          father[fx]=fy;
         }
     }
     cout<<ans<<endl;
}

int main()
{
    while(cin>>n)
    {
     len=0;
     for (int i=0;i<n;i++)
      for (int j=0;j<n;j++)
      {
          int x;    
          cin>>x;
          if (i==j) continue;
          node p;
          p.x=i;p.y=j;p.value=x;
          edge[++len]=p;
      }
     kruskal();
    }
    
    return 0;
}

posted on 2009-10-07 15:26 Vincent 阅读(481) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理