学步园

诶,,,要是以前养成了那么好的习惯就好了,,,现在再改是不是就有点晚了呢???

我才不相信会晚呢,,,还有很长时间呢,,够我吧这个习惯给改掉了 呼呼

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#define inf 0x3fffffff

using namespace std;

int N;

int map[111][111];

int visit[111];

int dis[111];

int prim()
{
	for (int i = 1; i <= N; i++)
	{
		dis[i] = inf;
	}
	dis[1] = 0;
	for (int i = 1; i <= N; i++)
	{
		int t = inf, pos;
		for (int j = 1; j <= N; j++)
		{
			if (!visit[j] && t > dis[j])
			{
				t = dis[j];
				pos = j;
			}
		}
		visit[pos] = 1;
		for (int j = 1; j <= N; j++)
		{
			if (!visit[j] && dis[j] > map[pos][j] && map[pos][j] != 0x3f3f3f3f)
			{
				dis[j] = map[pos][j];
			}
		}
	}
	int sum = 0;
	for (int i = 1; i <= N; i++)
	{
//		cout << dis[i] << endl;
		sum += dis[i];
	}
	return sum;
}
			

int main()
{
	while (scanf ("%d" , &N), N)
	{
		memset (visit, 0 , sizeof (visit));
		memset (map, 0x3f , sizeof(map));
		int M = N * (N-1) / 2;
		int a, b, val;
		for (int i = 1; i <= M; i++)
		{
			scanf ("%d %d %d", &a, &b ,&val);
			if (map[a][b] > val)
			{
				map[a][b] = val;
				map[b][a] = val;
			}
		}
		int ans = prim();
		printf ("%d\n", ans);
	}
	return 0;
}

再来一个标准排版的krusacal()算法:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <algorithm>

using namespace std;

int N;//N represents the number of points;

int M;// M represents the number of edges;

int set[111];

struct Edge{
	int a;
	int b;
	int val;
}e[22222];

bool cmp(Edge a, Edge b)
{
	return a.val < b.val;
}

int find(int x)
{
	return set[x] = (x == set[x]? x : find(set[x]));//这个也是需要记忆加理解的 
}

int kruscal()
{
	for (int i = 1; i <= N; i++)
	{
		set[i] = i;
	}
	int sum = 0;
	for (int i = 1; i <= M; i++)//这一点是需要注意的,可不是小于点的个数,而是小于等于边的个数 
	{
		int x = find(e[i].a);
		int y = find(e[i].b);
		int val = e[i].val;
		if (x != y)
		{
//			cout << x << " " << y << endl;
//			cout << val << endl;
			set[x] = y;
			sum += val;
		}
	}
	return sum;
}
			
int main()
{
	while (scanf ("%d", &N), N)
	{
		int a, b, val;
		M = N * (N-1) / 2;
		for (int i = 1; i <= M; i++)
		{
			scanf ("%d %d %d", &e[i].a, &e[i].b, &e[i].val);//为什么不需要处理重边的呢? 
		}
		sort(e + 1, e + M + 1, cmp);//这也需要注意的,注意sort里面的参数都是地址 
		int ans = kruscal();
		printf ("%d\n", ans);
	}
	return 0;
}