Liny_@NotePad

沉迷ACG中

Bad Cowtractors

YOYO posted @ 2008年11月25日 23:33 in 【ICPC】解题报告 with tags prim 最大生成树 , 2001 阅读

pku 2377：http://acm.pku.edu.cn/JudgeOnline/problem?id=2377

很基础的一道题，输入N和M，表示有N个结点和M条路径，求这个图的最大生成树。

题目意思很明显了，但是注意有重边的情况，此时应该输出权较大的结果，当不能连通时输出-1。

  1. #include<iostream>
  2. using namespace std;
  3. int n;
  4. int edge[1005][1005];
  5. bool visit[1005];
  6. int sum;
  7.  
  8. void prim(){
  9.         int i,j,k;
  10.         int lowcost[1005];
  11.         for (i=0;i<n;i++){
  12.                 lowcost[i]=edge[0][i];
  13.         }
  14.         visit[0]=true;
  15.         for (i=1;i<n;i++){
  16.                 j=0;
  17.                 while (visit[j]) j++;
  18.                 for (k=0;k<n;k++)
  19.                         if ((!visit[k])&&(lowcost[k]>lowcost[j])) j=k;
  20.                 if(lowcost[j]==0)break;
  21.                 sum += lowcost[j];
  22.                 visit[j]=true;
  23.                 for (k=0;k<n;k++)
  24.                         if (!visit[k]&&(edge[j][k]>lowcost[k])){
  25.                                 lowcost[k]=edge[j][k];
  26.                         }
  27.         }
  28. }
  29.  
  30. int main(){
  31.         int m;
  32.         cin>>n>>m;
  33.         int i,j,t;
  34.         bool flag = true;
  35.         for(i=0;i<n;i++){
  36.                 visit[i]=false;
  37.                 for(j=0;j<n;j++){
  38.                         edge[i][j]=0;
  39.                 }
  40.         }
  41.         while(m--){
  42.                 cin>>i>>j>>t;
  43.                 if(t>edge[i-1][j-1]){
  44.                         edge[i-1][j-1]=edge[j-1][i-1]=t;
  45.                 }
  46.         }
  47.         prim();
  48.         for(i=1;i<n;i++){
  49.                 if(!visit[i]){
  50.                         cout<<-1<<endl;
  51.                         flag = false;
  52.                         break;
  53.                 }
  54.         }
  55.         if(flag)cout<<sum<<endl;
  56.         return 0;
  57. }
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter