POJ 2485 C++ （图论）

//faint ,太汗了，今天上午用prim水到手软
#include<iostream>
using namespace std;
int  array[501][501],total;
int  used[501],dis[501];
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;
           if(min>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 m,n,sum;
      freopen("in.txt","r",stdin);
      freopen("out.txt","w",stdout);
      scanf("%d",&m);
     while(m--)
      { scanf("%d",&n);
        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:09 蜗牛 阅读(956) 评论(0)  编辑 收藏 引用 所属分类: ACM ICPC