 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| 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 | |||||||||
注意有重边In Reply To:搞不懂为什么会WA Posted by:plator at 2007-07-06 10:13:42 >
> #include<iostream>
> using namespace std;
> int **Matrix;
> int sum=0;
> int n;
>
> void Prim()
> {
> int max,j,index,i;
> int *N;
> N=new int[n];
> int *c;
> c=new int[n];
> bool *b;
> b=new bool [n]; //1 is tree node,0 is not tree node
> b[0]=1;
> for(i=1;i<n;i++)
> b[i]=0;
> for(i=0;i<n;i++)
> {
> if(Matrix[0][i]!=-1)
> {
> N[i]=0;
> c[i]=Matrix[0][i];
> }
> else
> c[i]=-1;
> }
> for(i=0;i<n-1;i++)
> {
> //search the max edge in array c
> max=-1;
> index=0;
> for(j=1;j<n;j++)
> {
> if(max<c[j] && b[j]==0)
> {
> index=j;
> max=c[j];
> }
> }
> if(c[index]==-1)
> {
> sum=-1;
> return;
> }
> b[index]=1;
> sum=sum+max;
> for(j=0;j<n;j++) //update N and C
> {
> if(Matrix[index][j]!=-1 && b[j]==0)
> {
> if(Matrix[index][j]>c[j])
> {
> N[j]=index;
> c[j]=Matrix[index][j];
> }
> }
> }
> }
> }
> int main()
> {
> int m,x,y,w;
> cin>>n>>m;
> Matrix=new int*[n];
> int i;
> for(i=0;i<n;i++)
> Matrix[i]=new int[n];
> for(x=0;x<n;x++)
> {
> for(y=0;y<n;y++)
> Matrix[x][y]=-1; // 初始化邻接矩阵
> }
> for(i=0;i<m;i++) //输入数据
> {
> cin>>x>>y;
> cin>>Matrix[x-1][y-1];
> Matrix[y-1][x-1]=Matrix[x-1][y-1];
> }
> Prim();
> cout<<sum<<endl;
> }
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
