亚洲精品国产成人99久久,欧美精品九九99久久在观看,97久久精品国产精品青草

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 閱讀(486) 評論(0) 編輯收藏引用所屬分類: 數據結構與算法

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: P3368 P2352 dinic P3273 P2104 ctsc2000 丘比特的煩惱 usaco 4.3 lgame P3267 P1276 P1837

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

巢穴

My Links

Blog Stats

News

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

文章檔案

Link

搜索

最新評論

閱讀排行榜

評論排行榜

P1258 By kruskal