Liny_@NotePad

沉迷ACG中

Agri-Net

YOYO posted @ 2008年11月24日 07:35 in 【ICPC】解题报告 with tags 最小生成树 prim , 2085 阅读

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

最小生成树。prim或kruskal。由于prim比较好敲……幸好有做这题不然就忘了准备模板了囧

  1. #include<iostream>
  2. #define MAX 200000
  3. using namespace std;
  4. int n;
  5. int edge[105][105];
  6.  
  7. int prim(){
  8.         int lowcost[105],mincost;
  9.         int i,j,k;
  10.         for(i=1;i<n;i++){
  11.                 lowcost[i]=edge[0][i];
  12.         }
  13.         lowcost[0]=0;
  14.         int sum = 0;
  15.         for(i=1;i<n;i++){
  16.                 mincost = MAX;
  17.                 j=1;
  18.                 k=1;
  19.                 while(j<n){
  20.                         if(lowcost[j]!=0&&lowcost[j]<mincost){
  21.                                 mincost = lowcost[j];
  22.                                 k = j;
  23.                         }
  24.                         j++;
  25.                 }
  26.                 sum += mincost;
  27.                 lowcost[k] = 0;
  28.                 for(j=1;j<n;j++){
  29.                         if(edge[k][j]<lowcost[j]){
  30.                                 lowcost[j]=edge[k][j];
  31.                         }
  32.                 }
  33.         }
  34.         return sum;
  35. }
  36.  
  37. int main(){
  38.         while(cin>>n){
  39.                 for(int i=0;i<n;i++){
  40.                         for(int j=0;j<n;j++){
  41.                                 cin>>edge[i][j];
  42.                         }
  43.                 }
  44.                 cout<<prim()<<endl;
  45.         }
  46.         return 0;
  47. }

 

 

Small_feed 评论 (0)

登录 *


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