| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:前一题还是用prim做的AC了 ,这题就是简单的prim,测了多组数据了,就是过不了,帮我看看,多谢!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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator