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

Re:前一题还是用prim做的AC了 ,这题就是简单的prim,测了多组数据了,就是过不了,帮我看看,多谢!

Posted by 2007011268 at 2008-11-29 13:17:35 on Problem 1258
In Reply To:前一题还是用prim做的AC了 ,这题就是简单的prim,测了多组数据了,就是过不了,帮我看看,多谢! Posted by:oboaix at 2008-03-15 22:08:04
这是我的代码,也总是wa,疯了……

# include <iostream>
# include <vector>
using namespace std;
int a[101][101];          
vector<int> U,V;         
void input(int);     
int shu(int n);    
int main()
{
	int n;
    while(cin)
	{
		cin>>n;
		input(n);
		cout<<shu(n)<<endl;   
		U.clear();
		V.clear();
	}
	return 0;
}
void input(int n)
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
}
int shu(int n)
{
	int answer=0;
	for(int i=2;i<=n;i++)
		V.push_back(i);
	U.push_back(1);

	int min=100001,mini=0,minj=0,num=1;
	while(num!=n)
	{
		min=100001;
		for(size_t i=0;i<U.size();i++)
			for(size_t j=0;j<V.size();j++)
			{
				if(a[U[i]][V[j]]<min)
				{
					min=a[U[i]][V[j]];
					mini=U[i];
					minj=V[j];
				}
			}
			answer+=a[mini][minj];
			U.push_back(minj);
			num++;
			for(vector<int>::iterator iter=V.begin();iter!=V.end();++iter)
			{
				if(*iter==minj)
				{
					V.erase(iter);
					break;
				}
			}
		
	}
	return answer;
}

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