最小生成树。不算难，可是由于太久没写了，而且Prim算法跟Dijkstra框架又差不多，导致错了几次：
1. Dijkstra每次找到离集合S最近的点v后，是一次Relax操作（见前面的单源最短路系列），而Prim只是简单地将较小的边权赋值给v，作为新的估计值。
2. 标准c++ 中int的存储位数为32位。
3. 使用memset要小心，对于int数组a来说，memset(a,k,sizeof(a))，当k=-1,0,1时可以用，但k不为以上值时，会出错，得用循环赋值。
另外最小生成树（MST）有以下重要性质：
Lemma : 对于所有生成树T来说，MST不但所有边权值之和最小，而且这些边权值的最大值在所有生成树中也是最小的。证明还没想好。迟些再补上。
#include <iostream>
#include <list>
#define INF 1000001
using namespace std;
const int maxn=1001;
int g[maxn][maxn];
long close[maxn];
bool visit[maxn];
int trace[maxn]; // 存储生成树
int n,m;
void prim()
{
//int total=0;
int minedge=-1;
int i,j,k;
memset(visit,0,sizeof(visit));
for(i=1;i<n;i++) close[i]=1000001;
memset(trace,-1,sizeof(trace));
visit[0]=1;
close[0]=0;
for(i=1;i<n;i++)
{
if(g[0][i]>0)
{
close[i]=g[0][i];
trace[i]=0;
}
}
for(i=0;i<n-1;i++)
{
int index;
int mindis=1000001;
for(j=1;j<n;j++)
{
if(visit[j]==0 && close[j]<mindis)
{
mindis=close[j];
index=j;
}
}
visit[index]=1;
minedge=(close[index]>minedge)?close[index]:minedge;
for(j=1;j<n;j++)
{
if(g[index][j]>0 && visit[j]==0 && close[j]>g[index][j])
{
close[j]=g[index][j];
trace[j]=index;
}
}
}
printf("%d\n",minedge);
printf("%d\n",n-1);
for(i=1;i<n;i++)
{
if(trace[i]!=-1) printf("%d %d\n",trace[i]+1,i+1);
}
}
int main()
{
freopen("in.txt","r",stdin);
memset(g,0,sizeof(g));
scanf("%d%d",&n,&m);
int i,j,k,w;
for(i=0;i<m;i++)
{
scanf("%d%d%d",&j,&k,&w);
g[j-1][k-1]=g[k-1][j-1]=w;
}
prim();
return 1;
}