最小生成树。不算难,可是由于太久没写了,而且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
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int maxn=1001;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int g[maxn][maxn];
long close[maxn];
bool visit[maxn];
int trace[maxn]; // 存储生成树
int n,m;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void prim()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
//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++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(g[0][i]>0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
close[i]=g[0][i];
trace[i]=0;
}
}
for(i=0;i<n-1;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
int index;
int mindis=1000001;
for(j=1;j<n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(visit[j]==0 && close[j]<mindis)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
mindis=close[j];
index=j;
}
}
visit[index]=1;
minedge=(close[index]>minedge)?close[index]:minedge;
for(j=1;j<n;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(g[index][j]>0 && visit[j]==0 && close[j]>g[index][j])
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
close[j]=g[index][j];
trace[j]=index;
}
}
}
printf("%d\n",minedge);
printf("%d\n",n-1);
for(i=1;i<n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
if(trace[i]!=-1) printf("%d %d\n",trace[i]+1,i+1);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
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++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
scanf("%d%d%d",&j,&k,&w);
g[j-1][k-1]=g[k-1][j-1]=w;
}
prim();
return 1;
}