最小生成樹。不算難，可是由于太久沒(méi)寫了，而且Prim算法跟Dijkstra框架又差不多，導(dǎo)致錯(cuò)了幾次：
1. Dijkstra每次找到離集合S最近的點(diǎn)v后，是一次Relax操作（見(jiàn)前面的單源最短路系列），而Prim只是簡(jiǎn)單地將較小的邊權(quán)賦值給v，作為新的估計(jì)值。
2. 標(biāo)準(zhǔn)c++ 中int的存儲(chǔ)位數(shù)為32位。
3. 使用memset要小心，對(duì)于int數(shù)組a來(lái)說(shuō)，memset(a,k,sizeof(a))，當(dāng)k=-1,0,1時(shí)可以用，但k不為以上值時(shí)，會(huì)出錯(cuò)，得用循環(huán)賦值。
另外最小生成樹（MST）有以下重要性質(zhì)：
Lemma : 對(duì)于所有生成樹T來(lái)說(shuō)，MST不但所有邊權(quán)值之和最小，而且這些邊權(quán)值的最大值在所有生成樹中也是最小的。證明還沒(méi)想好。遲些再補(bǔ)上。
#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]; // 存儲(chǔ)生成樹
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;
}