poj2352，poj1287

最小生成樹

 #include?<iostream>
#include?<cstdio>
#include?<cstdlib>
#include?<cstring>
using?namespace?std;

#define?maxn?55
#define?inf?0x3f3f3f3f

int?n,?m;
int?vis[maxn];
int?lowc[maxn];
int?cost[maxn][maxn];

int?prim()
{
????int?i,?j,?p;
????int?minc,?res?=?0;
????memset(vis,?0,?sizeof(vis));
????vis[0]?=?1;
????for?(i?=?1;?i?<?n;?i++)
????????lowc[i]?=?cost[0][i];
????for?(i?=?1;?i?<?n;?i++)
????{
????????minc?=?inf;
????????p?=?-1;
????????for?(j?=?0;?j?<?n;?j++)
????????????if?((0?==?vis[j]?&&?minc?>?lowc[j]))
????????????{
????????????????minc?=?lowc[j];
????????????????p?=?j;
????????????}
????????if?(inf?==?minc)
????????????return?-1;
????????res?+=?minc;
????????vis[p]?=?1;
????????for?(j?=?0;?j?<?n;?j++)
????????????if?(0?==?vis[j]?&&?lowc[j]?>?cost[p][j])
????????????????lowc[j]?=?cost[p][j];
????}
????return?res;
}

void?input()
{
????scanf("%d",?&m);
????for?(int?i?=?0;?i?<?n;?i++)
????????for?(int?j?=?0;?j?<?n;?j++)
????????????cost[i][j]?=?inf;
????for?(int?i?=?0;?i?<?m;?i++)
????{
????????int?a,?b,?c;
????????scanf("%d%d%d",?&a,?&b,?&c);
????????a--;
????????b--;
????????if?(cost[a][b]?>?c)
????????????cost[a][b]?=?cost[b][a]?=?c;
????}
}

int?main()
{
????//freopen("t.txt",?"r",?stdin);
????while?(scanf("%d",?&n),?n)
????{
????????input();
????????printf("%d\n",?prim());
????}

????return?0;
}