随笔 - 62  文章 - 96  trackbacks - 0
<2006年10月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(7)

随笔分类(66)

随笔档案(62)

文章分类(31)

文章档案(32)

友情链接

最新随笔

积分与排名

  • 积分 - 210728
  • 排名 - 105

最新评论

阅读排行榜

评论排行榜

#include<cstdio>
const int MAX = 10000;
const int INF = 1000000;
int clo[MAX];
int low[MAX];
int c[MAX][MAX];
bool flag[MAX];
int beg[MAX],end[MAX];//记录生成树的每条边的两个顶点
int Prim(int n)
{
	int i, j, k, ans = 0, pair = 0;
	flag[1] = true;
	for(i = 2; i <= n; i++)
	{
		low[i] = c[1][i];
		clo[i] = 1;
		flag[i] = false;
	}
	for(i = 1; i < n; i++)
	{
		j = 1;
		int min = INF;
		for(k = 2; k <=n; k++)
		{
			if(low[k] < min && !flag[k])
			{
				min = low[k];
				j = k;
			}
		}
		flag[j] = true;
		beg[i] = j;
		end[i] = clo[j];
		ans += c[j][clo[j]];
		for(k = 2; k <= n; k++)
		{
			if(c[j][k] < low[k] && !flag[k])
			{
				low[k] = c[j][k];
				clo[k] = j;
			}
		}
	}
	return ans;
}
int main()
{
	int i, j, n, m;
	scanf("%d%d",&n,&m);
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <=n; j++)
		{
			c[i][j]=INF;
		}
	}
	return 0;
}
posted on 2006-10-13 23:48 beyonlin 阅读(2964) 评论(4)  编辑 收藏 引用 所属分类: acm之路

FeedBack:
# re: 最小生成树Prim算法 2007-07-18 14:36 jrl


排版很工整,界面也不错,支持!  回复  更多评论
  
# re: 最小生成树Prim算法 2007-07-22 03:04 beyonlin
谢谢!
以前由于浏览器问题没有显示“插入代码”的按钮,
所以代码都是手动贴上去的,呵呵~~  回复  更多评论
  
# re: 最小生成树Prim算法 2011-06-20 10:07 02
你确定这是C++代码??你这是在坑人吧。  回复  更多评论
  
# re: 最小生成树Prim算法 2011-06-30 11:54 beyonlin
@02
可以说是C代码
  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理