POJ 2485 Highways
标准的prim模板题，只是输出的不是最小生成树的总权值，而是MST中的最长边。
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define MAX 501
int n;
int value[MAX][MAX];
int dis[MAX];
bool flag[MAX];
int maxlen;
void prim ()
{
int i,j;
int mark;
memset(flag,false,sizeof(flag));
flag[1]=true;
for(i=1;i<=n;i++)
{
dis[i]=value[1][i];
}
for(i=1;i<n;i++)
{
int min=99999;
for(j=1;j<=n;j++)
{
if(!flag[j]&&dis[j]<=min)
{
min=dis[j];
mark=j;
}
}
flag[mark]=true;
if(min>maxlen)
maxlen=min;
for(j=1;j<=n;j++)
{
if(!flag[j]&&value[mark][j]<dis[j])
dis[j]=value[mark][j];
}
}
}
int main ()
{
int testcase;
int i,j,k;
scanf("%d",&testcase);
for(i=1;i<=testcase;i++)
{
scanf("%d",&n);
for(j=1;j<=n;j++)
{
for(k=1;k<=n;k++)
{
scanf("%d",&value[j][k]);
}
}
maxlen=0;
prim();
printf("%d\n",maxlen);
}
return 0;
}
POJ 1861 Network
刚才又重新看了一遍题，output简直就是个误导，题目要求联通方案中最长的边最小，其实只要输出最小生成树中的最长边就可以了。
除了这个，剩下的问题就是标准的
Kruskal模板,输出最长边和具体的生成树方案即可。
#include<iostream>
#include<algorithm>
using namespace std;
struct element
{
int a;
int b;
int value;
}edge[15001];
element record[15001];
int f[1001];
int r[1001];
bool cmp(element a,element b)
{
return a.value<b.value;
}
int find(int n)
{
if(f[n]==n)
return n;
else
f[n]=find(f[n]);
return f[n];
}
int Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)
return 0;
else if(r[a]<=r[b])
{
f[a]=b;
r[b]+=r[a];
}
else
{
f[b]=a;
r[a]+=r[b];
}
return 1;
}
int main ()
{
int num=0;
int max=0;
int pos=1;
int sum=0;
int n,m;
int i,j;
scanf ( "%d%d", &n, &m );
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].value);
}
for(i=1;i<=n;i++)
{
f[i]=i;
r[i]=1;
}
sort(edge+1,edge+m+1,cmp);
for(i=1;i<=m;i++)
{
if(Union(edge[i].a,edge[i].b)==1)
{
num++;
if(edge[i].value>max)
max=edge[i].value;
record[pos].a=edge[i].a;
record[pos].b=edge[i].b;
sum+=edge[i].value;
pos++;
}
if(num==n-1)
break;
}
printf("%d\n%d\n",max,pos-1);
for(i=1;i<=pos-1;i++)
{
printf("%d %d\n",record[i].a,record[i].b);
}
return 0;
}
POJ 2395 Out of Hay
还是求最小生成树的最长边，为什么呢？我想了1分钟，因为kruskal算法是从按照边权从小到大的顺序选择边的，如果形成环路，那么我肯定选择之前选过的那条边，当我不断添加边使得整个图联通的时候，最后一条边一定是任何方案中最小的。感觉这个题目并不是纯粹的最小生成树，但是却暗藏有最小生成树算法的精神。
#include<iostream>
#include<algorithm>
using namespace std;
struct element
{
int a;
int b;
int value;
}edge[10005];
int f[2005];
int r[2005];
bool cmp(element a,element b)
{
return a.value<b.value;
}
int find(int n)
{
if(f[n]==n)
return n;
else
f[n]=find(f[n]);
return f[n];
}
int Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)
return 0;
else if(r[a]<=r[b])
{
f[a]=b;
r[b]+=r[a];
}
else
{
f[b]=a;
r[a]+=r[b];
}
return 1;
}
int main ()
{
int num=0;
int max=0;
int n,m;
int i,j;
while ( scanf ( "%d%d", &n, &m ) != EOF )
{
num=0;
max=0;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].value);
}
for(i=1;i<=n;i++)
{
f[i]=i;
r[i]=1;
}
sort(edge+1,edge+m+1,cmp);
for(i=1;i<=m;i++)
{
if(Union(edge[i].a,edge[i].b)==1)
{
num++;
if(edge[i].value>max)
max=edge[i].value;
}
if(num==n-1)
break;
}
printf("%d\n",max);
}
return 0;
}
POJ 2377 Bad Cowtractors
最大生成树，由于给出的是边的信息，所以最好用kruskal算法（还能避免重边），注意当图不连通时要输出-1。
另外这个题给我一点额外的启示，判断一个无向图是不是联通可以直接用kruskal呵。扩展一下，如果求任意两点是否连通可以用floyd求传递闭包。
#include<iostream>
#include<algorithm>
using namespace std;
struct element
{
int a;
int b;
int value;
}edge[20001];
int f[1001];
int r[1001];
int cmp(const void *a,const void *b)
{
return -((*(element*)a).value-(*(element*) b).value);
}
int find(int n)
{
if(f[n]==n)
return n;
else
f[n]=find(f[n]);
return f[n];
}
int Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)
return 0;
else if(r[a]<=r[b])
{
f[a]=b;
r[b]+=r[a];
}
else
{
f[b]=a;
r[a]+=r[b];
}
return 1;
}
int main ()
{
int num=0;
int sum=0;
int n,m;
int i,j;
scanf ( "%d%d", &n, &m );
sum=0;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].value);
}
for(i=1;i<=n;i++)
{
f[i]=i;
r[i]=1;
}
qsort(edge+1,m,sizeof(edge[1]),cmp);
for(i=1;i<=m;i++)
{
if(Union(edge[i].a,edge[i].b)==1)
{
num++;
sum+=edge[i].value;
}
}
if(num==n-1)
printf("%d\n",sum);
else
printf("-1\n");
return 0;
}
POJ 2421 Constructing Roads
已经修好的路代价为0，此后直接prim就最小代价既可。
呵呵 再贴一个第一次做这个题时候留下的帖子 现在看看挺幼稚的 呵呵，大家不要见笑。
Posted by
abilitytao at 2009-01-20 19:34:19 on
Problem 2421
离散课上上过 所以就慕名而来了 呵呵
原来课上讲的和实际编起来差距是很大的 从最初的思想到最后的代码实现 我用了2个多小时的时间 参阅过2本书 可见现在的ACM和刚入队时已经不同了 要逐渐适应起来丫
再说说正题吧
我怎么感觉prim 算法和 最短路径算法这么像？呵呵 也许色即是空 空即是色 万物是相互转化的吧 点就是线 线就是点 善哉善哉
看看时间，应该是大二上的寒假做的吧，再次纪念第一道MST。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 101
int n;
int map[N][N];
int dis[N];
int visit[N];
int result;
void prim ()
{
result=0;
int i;
int j;
int flag;
int min=999999999;
visit[1]=1;
for(i=1;i<=n;i++)
{
dis[i]=map[1][i];
}
for(i=1;i<n;i++)
{
min=999999999;
for(j=1;j<=n;j++)
{
if(!visit[j]&&dis[j]<min){min=dis[j],flag=j;}
}
visit[flag]=1;result+=dis[flag];
for(j=1;j<=n;j++)
if(!visit[j]&&map[flag][j]<dis[j]){dis[j]=map[flag][j];}
}
}
int main ()
{
int testcase;
int a,b;
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
}
}
scanf("%d",&testcase);
for(i=1;i<=testcase;i++)
{
scanf("%d%d",&a,&b);
map[a][b]=0;
map[b][a]=0;
}
prim();
printf("%d\n",result);
return 0;
}
POJ 1679 The Unique MST
问最小生成树是不是唯一，转化成求次最小生成树（注意不连通的情况），当时认为这题不适合新手做，所以直到昨天才A掉这个题。做法是先求出最小生成树，然后枚举删边，求剩余边的最小生成树，求出最小的那个即为次最小生成树。如果次最小生成树权值=原权值，说明MST不唯一，否则唯一输出数值。
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 101
#define INF 100000000
struct node
{
int u;
int v;
int len;
bool operator <(node other)
{
return len<other.len;
}
}edge[MAX*MAX];
int f[MAX];
int r[MAX];
int a[MAX];
int p;
int find(int n)
{
if(f[n]==n)
return n;
else
f[n]=find(f[n]);
return f[n];
}//查找函数，并压缩路径
int Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)
return 0;
else if(r[a]<=r[b])
{
f[a]=b;
r[b]+=r[a];
}
else
{
f[b]=a;
r[a]+=r[b];
}
return 1;
}//合并函数，如果属于同一分支则返回0，成功合并返回1
int mincost=0;
int kruskral(int n,int m)
{
mincost=0;
int temp=INF;
p=0;
int i,j;
for(i=1;i<=n;i++)
{
f[i]=i;
r[i]=1;
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].len);
}
sort(edge+1,edge+1+m);
int num=0;
for(i=1;i<=m;i++)
{
if(Union(edge[i].u,edge[i].v))
{
num++;
p++;
a[p]=i;
mincost+=edge[i].len;
}
if(num==n-1)
break;
}
int secmincost;
for(i=1;i<=n-1;i++)
{
secmincost=0;
num=0;
for(j=1;j<=n;j++)
{
f[j]=j;
r[j]=1;
}
for(j=1;j<=m;j++)
{
if(j==a[i])
continue;
if(Union(edge[j].u,edge[j].v))
{
num++;
secmincost+=edge[j].len;
}
if(num==n-1)
break;
}
if(num==n-1&&secmincost<temp)
temp=secmincost;
}
if(temp==mincost)
return 0;
else
return 1;
}
int main()
{
int testcase;
int i;
int n,m;
scanf("%d",&testcase);
for(i=1;i<=testcase;i++)
{
scanf("%d%d",&n,&m);
if(kruskral(n,m))
printf("%d\n",mincost);
else
printf("Not Unique!\n");
}
return 0;
}
POJ 1751 Highways
还是Highways???难道Highways和最小生成树那么有缘？呵呵
给定边，求出方案。设给定的边的权值是0。可以证明他们一定会被选中
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define MAX 1001
int record[1001];
int n;
double value[MAX][MAX];
double dis[MAX];
bool flag[MAX];
double lenth(int x,int y,int k,int j)
{
double len;
len=sqrt(((double)k-(double)x)*((double)k-(double)x)+((double)j-(double)y)*((double)j-(double)y));
return len;
}
struct dot
{
int x;
int y;
}dotset[1001];
dot record2[1001];
int pos=0;
void prim ()
{
int i,j;
int mark=0;
memset(flag,false,sizeof(flag));
flag[1]=true;
for(i=1;i<=n;i++)
{
dis[i]=value[1][i];
}
for(i=1;i<=n;i++)
record[i]=1;
for(i=1;i<n;i++)
{
double min=999999999;
for(j=1;j<=n;j++)
{
if(!flag[j]&&dis[j]<=min)
{
min=dis[j];
mark=j;
}
}
if(min!=0)
{
pos++;
record2[pos].x=record[mark];
record2[pos].y=mark;
}
dis[mark]=min;flag[mark]=true;
for(j=1;j<=n;j++)
{
if(!flag[j]&&value[mark][j]<dis[j])
{
dis[j]=value[mark][j];
record[j]=mark;
}
}
}
}
int main ()
{
int m;
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&dotset[i].x,&dotset[i].y);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
value[i][j]=lenth(dotset[i].x,dotset[i].y,dotset[j].x,dotset[j].y);
}
}
cin>>m;
for(i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
value[u][v]=0;
value[v][u]=0;
}
prim();
for(i=1;i<=pos;i++)
printf("%d %d\n",record2[i].x,record2[i].y);
return 0;
}
POJ 1258 Agri-Net
最经典的MST，建议新手先做此题。
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define MAX 101
int n;
int value[MAX][MAX];
int dis[MAX];
bool flag[MAX];
int result;
void prim ()
{
int i,j;
int mark;
result=0;
memset(flag,false,sizeof(flag));
flag[1]=true;
for(i=1;i<=n;i++)
{
dis[i]=value[1][i];
}
for(i=1;i<n;i++)
{
int min=999999999;
for(j=1;j<=n;j++)
{
if(!flag[j]&&dis[j]<=min)
{
min=dis[j];
mark=j;
}
}
flag[mark]=true;result+=dis[mark];
for(j=1;j<=n;j++)
{
if(!flag[j]&&value[mark][j]<dis[j])
dis[j]=value[mark][j];
}
}
}
int main ()
{
int i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&value[i][j]);
}
}
prim();
printf("%d\n",result);
}
return 0;
}
POJ 1251 Jungle Roads
输入的时候有些字母，构图的时候要转换一下。
#include<iostream>
#include<algorithm>
using namespace std;
struct element
{
int a;
int b;
int value;
}edge[100];
int f[30];
int r[30];
int cmp(const void *a,const void *b)
{
return (*(element*)a).value-(*(element*)b).value;
}
int find(int n)
{
if(f[n]==n)
return n;
else
f[n]=find(f[n]);
return f[n];
}
int Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)
return 0;
else if(r[a]<=r[b])
{
f[a]=b;
r[b]+=r[a];
}
else
{
f[b]=a;
r[a]+=r[b];
}
return 1;
}
int num=0;
int sum=0;
int main ()
{
int pos;
int n,m,k;
int i,j;
char temp[10];
while (cin>>n)
{
pos=0;
num=0;
sum=0;
if(n==0)
break;
for(i=1;i<n;i++)
{
cin>>temp;
cin>>m;
for(j=1;j<=m;j++)
{
pos++;
cin>>temp;
cin>>k;
edge[pos].a=i;
edge[pos].b=temp[0]-64;
edge[pos].value=k;
}
}
for(i=1;i<=n;i++)
{
f[i]=i;
r[i]=1;
}
qsort(edge+1,pos,sizeof(edge[1]),cmp);
for(i=1;i<=pos;i++)
{
if(Union(edge[i].a,edge[i].b)==1)
{
num++;
sum+=edge[i].value;
}
if(num==n-1)
break;
}
printf("%d\n",sum);
}
return 0;
}
POJ 3625 Building Roads
非常朴素的prim ^_^
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define MAX 1001
int n;
double value[MAX][MAX];
double dis[MAX];
bool flag[MAX];
double result;
double lenth(int x,int y,int k,int j)
{
double len;
len=sqrt(((double)k-(double)x)*((double)k-(double)x)+((double)j-(double)y)*((double)j-(double)y));
return len;
}
struct dot
{
int x;
int y;
}dotset[1001];
void prim ()
{
int i,j;
int mark;
result=0;
memset(flag,false,sizeof(flag));
flag[1]=true;
for(i=1;i<=n;i++)
{
dis[i]=value[1][i];
}
for(i=1;i<n;i++)
{
double min=999999999;
for(j=1;j<=n;j++)
{
if(!flag[j]&&dis[j]<=min)
{
min=dis[j];
mark=j;
}
}
dis[mark]=min;flag[mark]=true;result+=dis[mark];
for(j=1;j<=n;j++)
{
if(!flag[j]&&value[mark][j]<dis[j])
dis[j]=value[mark][j];
}
}
}
int main ()
{
int m;
int i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
{
scanf("%d%d",&dotset[i].x,&dotset[i].y);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
value[i][j]=lenth(dotset[i].x,dotset[i].y,dotset[j].x,dotset[j].y);
}
}
for(i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
value[u][v]=0;
value[v][u]=0;
}
prim();
printf("%.2f\n",result);
return 0;
}
POJ 1789 Truck History
题目里没数字，但是很容易知道每个车只有一个来源，说明没有环，所以一定是一个树，quality要最大，说明分母最小，故：最小生成树
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct node
{
char name[7];
};
node a[2001];
int camp(int i,int j)
{
int num=0;
int k;
for(k=0;k<7;k++)
{
if(a[i].name[k]!=a[j].name[k])
num++;
}
return num;
}
#define N 2001
int n;
int map[N][N];
int dis[N];
int visit[N];
int result;
void prim ()
{
memset(visit,0,sizeof(visit));
result=0;
int i;
int j;
int flag;
int min=999999999;
visit[1]=1;
for(i=1;i<=n;i++)
{
dis[i]=map[1][i];
}
for(i=1;i<n;i++)
{
min=999999999;
for(j=1;j<=n;j++)
{
if(!visit[j]&&dis[j]<min){min=dis[j],flag=j;}
}
visit[flag]=1;result+=dis[flag];
for(j=1;j<=n;j++)
if(!visit[j]&&map[flag][j]<dis[j]){dis[j]=map[flag][j];}
}
}
int main ()
{
int i,j,k;
while(cin>>n)
{
if(n==0)
break;
for(i=1;i<=n;i++)
cin>>a[i].name;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
map[i][j]=camp(i,j);
}
}
prim();
printf("The highest possible quality is 1/%d.\n",result);
}
}
北京赛区的经典题目，最优比率生成树，传说中楼哥1A的G题。。。
什么是最优比率生成树呢？说白了很简单，已知一个完全图，每条边有两个参数（b和c），求一棵生成树，使(∑xi×ci)/(∑xi×bi)最小，其中xi当第i条边包含在生成树中时为1，否则为0。其实也可以看成一个0，1的整数规划问题。
我的做法是LRJ《算法艺术与信息学竞赛》中介绍的二分，详细的证明请看书，这里只是简单的介绍一下核心的方法：
1.首先找出这个比率的最小值和最大值 front,rear
2.求mid=(front+reat)/2
3.用 ci-mid*bi 重新构图
4.求出新图的最小生成树权值之和
5.如果权值等于0,mid就是我们要求的比率，结束。如果权值>0,front=mid,如果权值<0,rear=mid,跳回2继续循环。
不过这个算法对精度的要求比较高，我用0.001就错了，0.00001超时，只有0.0001AC,汗
另外时间效率也不高，3000MS的题，耗去了2500MS，看来这个算法还是有待改进。
下面是我的代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define MAX 1001
#define INF 1000000000
struct node
{
double x,y,h;
}dot[MAX];
inline double dis(double x1,double y1,double x2,double y2)
{
return sqrt( (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1) );
}
double graph[MAX][MAX];
inline void creat(int n,double l)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
graph[i][j]=fabs(dot[i].h-dot[j].h)-l*dis(dot[i].x,dot[i].y,dot[j].x,dot[j].y);
}
}
}
inline double prim(double graph[MAX][MAX],int n)
{
bool visit[MAX]={0};
int mark;
double dis[MAX];
double ans=0;
int i,j;
visit[1]=true;
for(i=1;i<=n;i++)
dis[i]=graph[1][i];
for(i=1;i<n;i++)
{
int minnum=INF;
for(j=1;j<=n;j++)
{
if(!visit[j]&&dis[j]<=minnum)
{
minnum=dis[j];
mark=j;
}
}
visit[mark]=true;
ans+=dis[mark];
for(j=1;j<=n;j++)
{
if(!visit[j]&&graph[mark][j]<dis[j])
dis[j]=graph[mark][j];
}
}
return ans;
}
int main()
{
int i,j;
int n;
double res;
while(scanf("%d",&n))
{
if(n==0)
break;
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&dot[i].x,&dot[i].y,&dot[i].h);
}
double front,rear;
front=0;
rear=100;//这个地方有点悬。。。
double mid;
double pre=0.0;
while(front<=rear)
{
mid=(front+rear)/2;
creat(n,mid);
res=prim(graph,n);
if(fabs(res-pre)<=0.0005)
break;
else if(res>0.0005)
front=mid;
else
rear=mid;
}
printf("%.3lf\n",mid);
}
return 0;
}
———————————————————————传说中的分割线————————————————————————————
终于在今天下午 使用迭代法将此题优化到282MS，呵呵 这名字让我又想起了数值分析。。。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define MAX 1001
#define INF 1000000000
struct node
{
double x,y,h;
}dot[MAX];
inline double dis(double x1,double y1,double x2,double y2)
{
return sqrt( (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1) );
}
double graph[MAX][MAX];
double c[MAX][MAX];
double s[MAX][MAX];
inline void creatcs(int n)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
c[i][j]=fabs(dot[i].h-dot[j].h);
s[i][j]=dis(dot[i].x,dot[i].y,dot[j].x,dot[j].y);
}
}
}
inline void creat(int n,double l)
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
graph[i][j]=c[i][j]-l*s[i][j];
}
}
}
double sumc;
double sums;
inline void prim(double graph[MAX][MAX],int n)
{
sumc=0;
sums=0;
bool visit[MAX]={0};
int mark;
int pre[MAX];
double dis[MAX];
int i,j;
visit[1]=true;
for(i=1;i<=n;i++)
{
dis[i]=graph[1][i];
pre[i]=1;
}
for(i=1;i<n;i++)
{
int minnum=INF;
for(j=1;j<=n;j++)
{
if(!visit[j]&&dis[j]<=minnum)
{
minnum=dis[j];
mark=j;
}
}
visit[mark]=true;
sumc+=c[pre[mark]][mark];
sums+=s[pre[mark]][mark];
for(j=1;j<=n;j++)
{
if(!visit[j]&&graph[mark][j]<dis[j])
{
dis[j]=graph[mark][j];
pre[j]=mark;
}
}
}
}
int main()
{
int i,j;
int n;
while(scanf("%d",&n))
{
if(n==0)
break;
for(i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&dot[i].x,&dot[i].y,&dot[i].h);
}
creatcs(n);
double prerate=30.0;
double rate=30.0;
while(true)
{
creat(n,rate);
prim(graph,n);
rate=sumc/sums;
if(fabs(rate-prerate)<0.001)
break;
prerate=rate;
}
printf("%.3lf\n",rate);
}
return 0;
}
POJ 1287 Networking.....Orz
此题再次证明了我的预感是正确的。。。Network...
#include<iostream>
#include<algorithm>
using namespace std;
struct element
{
int a;
int b;
int value;
}edge[15001];
int f[1001];
int r[1001];
bool cmp(element a,element b)
{
return a.value<b.value;
}
int find(int n)
{
if(f[n]==n)
return n;
else
f[n]=find(f[n]);
return f[n];
}
int Union(int x,int y)
{
int a=find(x);
int b=find(y);
if(a==b)
return 0;
else if(r[a]<=r[b])
{
f[a]=b;
r[b]+=r[a];
}
else
{
f[b]=a;
r[a]+=r[b];
}
return 1;
}
int main ()
{
int num=0;
int sum=0;
int n,m;
int i,j;
while(scanf ( "%d", &n))
{
if(n==0)
break;
scanf("%d",&m);
sum=0;
num=0;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].value);
}
for(i=1;i<=n;i++)
{
f[i]=i;
r[i]=1;
}
sort(edge+1,edge+m+1,cmp);
for(i=1;i<=m;i++)
{
if(Union(edge[i].a,edge[i].b)==1)
{
num++;
sum+=edge[i].value;
}
if(num==n-1)
break;
}
printf("%d\n",sum);
}
return 0;
}