POJ 1258 C++ （圖論）

//汗，模板真的很爽
//只是稍稍改了一下前一題的代碼，最小生成樹問題
#include<iostream>
using namespace std;
int  array[101][101],total;
int  used[101],dis[101];
void prim(int n)
{ int v,min;
  for(int i=1;i<=n;i++)
      {used[i]=0;
       dis[i]=array[1][i];
       }
       used[1]=1;
      while(true)
        {  min=INT_MAX;
            v=0;
            for(int i=1;i<=n;i++)
               if(!used[i] && dis[i]<min)
                 { min=dis[i];
                   v=i;
                  }
            if(v==0)
               break;
           total=total+min;
           used[v]=1;
           for(int j =1;j<=n;j++)
               if(!used[j] && dis[j]>array[v][j])
                  dis[j]=array[v][j];
        }  
  }                  

int main()
{int n,sum;
      freopen("in.txt","r",stdin);
      freopen("out.txt","w",stdout);
while((scanf("%d",&n))!=EOF)
      {for(int i=1;i<=n;i++)
           for(int j=1;j<=n;j++)
               scanf("%d",&array[i][j]);
      total=0;
      prim(n);
      printf("%d\n",total);
}  

  return 0;
}    

posted on 2008-11-27 00:11 蝸牛 閱讀(229) 評論(0)  編輯 收藏 引用 所屬分類: ACM ICPC