简单最小生成树，畅通project。这三道题目都是练习最小生成树的。
注意一下推断是否有通路时，kruskal能够推断每一个点的祖先是否同样。prim能够推断每一个点是否都加进集合里面了，也就是说是否都訪问过。
prim算法要把没有给的边初始化为MAX无穷大。
。。
代码：（kruskal）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#include<utility>
#include<functional>
#define MAX 0x7fffffff
using namespace std;
int p[105];
struct node
{
int i,j,len;
}gra[10005];
int find(int x)
{
return x == p[x]? x: p[x] = find(p[x]);
}
int cmp(const void *a,const void *b)
{
return ((node *)a)->len - ((node *)b)->len;
}
int m,n;
void kruskal()
{
int i,sum = 0;
for(i=1; i<=m; i++)
{
int x = find(gra[i].i);
int y = find(gra[i].j);
if(x != y)
{
sum += gra[i].len;
p[x] = y;
}
}
int flag = 0;
for(i=1; i<=n; i++)
{
if(find(1) != find(i))
{
flag = 1;
break;
}
}
if(flag)
cout << "?" << endl;
else
cout << sum << endl;
return ;
}
int main()
{
int i,j,a,b,c;
while(cin >> m >> n,m)
{
for(i=1; i<=m; i++)
{
cin >> a >> b >> c;
gra[i].i = a;
gra[i].j = b;
gra[i].len = c;
}
for(i=1; i<=n; i++)
p[i] = i;
qsort(gra+1,m,sizeof(gra[0]),cmp);
kruskal();
}
return 0;
}
代码：（prim）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#include<utility>
#include<functional>
#define MAX 0x7fffffff
using namespace std;
int gra[105][105];
int m,n;
void prim()
{
int visit[105],i,j,now,MIN,sum = 0;
int d[105];
memset(visit,0,sizeof(visit));
for(i=1; i<=n; i++)
d[i] = MAX;
d[1] = 0;
visit[1] = 1,now = 1;
for(i=2; i<=n; i++)
{
for(j=1; j<=n; j++)
if(!visit[j] && d[j]>gra[now][j])
d[j] = gra[now][j];
MIN = MAX;
for(j=1; j<=n; j++)
if(!visit[j] && MIN > d[j])
MIN = d[now = j];
visit[now] = 1;
sum += d[now];
}
int flag = 0;
for(i=1; i<=n; i++)
{
if(!visit[i])
{
flag = 1;
break;
}
}
if(flag)
cout << "?" << endl;
else
cout << sum << endl;
}
int main()
{
int i,j,a,b,c;
while(cin >> m >> n,m)
{
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
gra[i][j] = MAX;
for(i=1; i<=m; i++)
{
cin >> a >> b >> c;
gra[a][b] = gra[b][a] = c;
}
prim();
}
return 0;
}