May 10 ——Sunday——最小生成树1102

http://acm.hdu.edu.cn/showproblem.php?pid=1102

 

刚学的最小生成树,就拿这两道题练手了,呵呵

把已经修建的路径设置为0,就ok 了

 

#include<iostream>
#include<cstring>
using namespace std;
#define N 1005
#define maxn 0xffffff
int matrix[N][N],vis[N],low[N];
int n;
int prim()
{
 int i,j,pos,sum=0;
 vis[1]=1;
 pos=1;
 for(i=1;i<=n;i++)
  if(i!=pos)
      low[i]=matrix[pos][i];
 for(i=1;i<n;i++)
 {
  int temp=maxn;
  for(j=1;j<=n;j++)
  {
   if(!vis[j]&&low[j]<temp)
   {
    temp=low[j];
    pos=j;
   }
  }
  sum+=temp;
  vis[pos]=1;
  for(j=1;j<=n;j++)
  {
   if(!vis[j]&&low[j]>matrix[pos][j])
    low[j]=matrix[pos][j];
  }
 }
 return sum;
}
int main()
{
 int i,j,m,a,b,c;
 while(cin>>n)
 {
  memset(vis,0,sizeof(vis));
  for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
  {
   cin>>c;
   matrix[i][j]=matrix[j][i]=c;
  }
  cin>>m;
  for(j=1;j<=m;j++)
  {
    cin>>a>>b;
    matrix[a][b]=matrix[b][a]=0;
  }
  cout<<prim()<<endl;
 }
 return 0;
}

 


评论
热度 ( 5 )

© 现实给了梦想多少时间 | Powered by LOFTER