简单最小生成树，畅通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;

}