http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2144&cid=1186
这道题一开始是用prim算法做的，一直错一直错，后来问了帅郭改用Kruskal做才对，再后来问了ＴＨＨ和二货才改对的prim算法，是因为重边我没处理啊，上火
#include <cstdio>
#include <cstring>
#include<cstdlib>
#include<iostream>
using namespace std ;
#define oo (1<<28)
const int N = ;
int map[N][N],low[N],flag[N];//low数组是用来保留最小代价的；
//flag数组是用来标记的，找过得点就不再去找
int m,n;
int u,v,w ;
int prim()
{
int i,j,pos,min,ans=;
memset(flag,,sizeof(flag));
flag[]=;
pos=;
for(i = ; i <= n ; i++)
if(i != pos)
low[i] = map[pos][i];
for(i = ; i < n ; i++)
{
min=oo;
for(j = ; j <= n ; j++)
if(flag[j] == &&min>=low[j])
{
min = low[j];
pos = j ;
}
ans += min ;
flag[pos] = ;
for(j = ; j <= n ; j++)
if(flag[j] == &&low[j]>map[pos][j])
low[j]=map[pos][j];
}
return ans;
}
int main()
{
int ans;
while(scanf("%d %d",&n,&m)!=EOF)
{
for(int i = ; i < N ; i++)
{
for(int j = ; j < N ; j++)
{
map[i][j] = oo ;
}
}
for(int i = ; i <= m ; i++)
{
scanf("%d %d %d",&u,&v,&w);
if(map[u][v] >w)//防止重边出现保留小的重边
map[u][v] = map[v][u] = w ;
}
ans = prim();
printf("%d\n",ans);
}
return ;
}
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std ;
const int MAXN = ;
const int MAX = ;
int EDG[MAX];
int sum;
struct node
{
int u ;
int v ;
int w ;
} map[MAXN],t;
int find(int x)
{
while(x!=EDG[x]){
x=EDG[x];
}
return x;
}
void Kruskal(int x,int y,int z)
{
x = find(x) ;
y = find(y) ;
if(x != y)
{
EDG[x] = y ;
sum += z;
}
}
int main()
{
int n,m,i,j;
while(~scanf("%d %d",&n,&m))
{
sum = ;
int k = ;
for(int i = ; i <= n ; i++)
EDG[i] = i ;
for(int i = ; i <= m ; i++)
scanf("%d %d %d",&map[i].u,&map[i].v,&map[i].w);
for(int i = ; i <= m- ; i++){
for(j = i+ ; j <= m ; j++){
if(map[i].w > map[j].w)
{
t = map[i] ;
map[i] = map[j];
map[j] = t ;
}
}
}
for(int i = ; i <= m ; i++)
Kruskal(map[i].u,map[i].v,map[i].w);
printf("%d\n",sum);
}
return ;
}