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