Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

算法大牛帮忙看看我的prim,wa了一天半了

Posted by shuangzai at 2009-08-18 23:16:06 on Problem 2421
用kruskal 47MS过了,用prim弄了一天半了还是WA ,大牛们帮忙看看吧!

#include<iostream>
#include <cmath>
using namespace std;

int n,a[102],p[102],c[102][102],sum=0;

bool flag[102][102];

void makeset()    //p[i]表根节点
{
	for(int i=1;i<=n;i++)
	{
		p[i]=i;
	
	}
}

int findset(int a)  //返回根节点
{
	while(a!=p[a])
		a=p[a];
	return a;
}

void unionset(int a,int b)//连接
{
	if(a==b)
		return;
	if(a > b)
		swap(a,b);
	int x = b;                     
	for(int i=b; i<=n; i++)  //将a与b所在链接起,即p[i]改为相等
        if(p[i] == x)
			p[b] = a;
}

int min_V(int k) //选出与已选点a[]相连的边中的最小边的顶点
{
	
	int min_v=0;
	int min_e=1001;
	
	for(int i=0; i<=k; i++)
		for(int j=1; j<=n; j++)
		{
			if(a[i]==j || flag[a[i]][j]==true) //同一点和已连接的过
				continue;
			
			if(findset(a[i]) == findset(j))    //形成回路的过
				continue;
			
			if (c[a[i]][j] < min_e)  //在与已选点a[]相连的边中选最小的
			{
				min_e = c[a[i]][j];
				min_v = j;
			}
			
		}
		
		flag[a[k]][min_v] = true; //标记已连接的
		flag[min_v][a[k]] = true;
		
		unionset(a[k],min_v);  //连接
		sum += min_e;
		return min_v;
}

int main()
{
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++)      
		for(int j=1;j<=n;j++)
			scanf("%d",&c[i][j]);
		
		int p;
		scanf("%d",&p);
		memset(flag,false,sizeof(flag)); //memset() 库函数置初值
		for(int k=0;k<p;k++)       //改已连接的边为0,当成无连接的边处理
		{
			int a,b;
			scanf("%d%d",&a,&b);
			c[a][b] = 0; 
			c[b][a] = 0;
		}
		
		makeset();  //建立根节点
		a[0] = 1;
		for(int t=1; t<n; t++)
			a[t] = min_V(t-1); //选点
		
		cout<<sum<<endl;	

}

/*
3
0 990 692
990 0 179
692 179 0
1
1 2

*/

/*
4
0 5 6 7
5 0 8 1
6 8 0 3
7 1 3 0
1
2 3
*/

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator