HDU 1233はやはり開通工程の最小生成ツリーです。
1788 ワード
タイトルの住所:http://acm.hdu.edu.cn/showproblem.php?pid=1233
標準的なKruskyalアルゴリズム。
コードは以下の通りです
標準的なKruskyalアルゴリズム。
コードは以下の通りです
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/
int n,m;//n , m ,
int visit[1005];
int parent[105];//
struct se
{
int x,y,w;
}edge[5055];
bool emp(se a,se b)
{
return a.w<b.w;
}
void UFset()
{
for(int i=0;i<=n;i++)
parent[i]=i;
}
int find(int x)
{
int r=x;
while(x!=parent[x])
x=parent[x];
while(r!=x)
{
int j=parent[r];
parent[r]=x;
r=j;
}
return x;
}
void Kruskal()
{
int i,j,count=0,sum=0;
UFset();//
for(i=0;i<m;i++)
{
int fx=find(edge[i].x);
int fy=find(edge[i].y);
if(fx!=fy)
{
count++;
parent[fx]=fy;
sum+=edge[i].w;
if(count==n-1)
break;
}
}
printf("%d
",sum);
}
int main()
{
int i,j;
while(cin>>n,n)
{
m=0;
int sum=n*(n-1)/2;
for(i=1;i<=sum;i++)
{
int a,b,t;
scanf("%d%d%d",&a,&b,&t);
if(a>b)// a<b
swap(a,b);
edge[m].x=a;
edge[m].y=b;
edge[m].w=t;
m++;
}
sort(edge,edge+m,emp);//
Kruskal();
}
return 520;
}