我要啦免费统计
http://acm.pku.edu.cn/JudgeOnline/problem?id=2485
最小生成树最长边,要数量不要质量,空虚的题目经验,5555
#include<iostream>
using namespace std;
int n;
#define MAXN 501
#define inf 65537
int map[MAXN][MAXN];//visited[N];
typedef int  elem_t;

elem_t prim(
int n,elem_t mat[][MAXN]){
    elem_t min[MAXN],ret
=0;
    
int v[MAXN],i,j,k;
    
for (i=0;i<n;i++)
        min[i]
=inf,v[i]=0;
        
    
for (min[j=0]=0;j<n;j++){
        
for (k=-1,i=0;i<n;i++)
            
if (!v[i]&&(k==-1||min[i]<min[k]))
                k
=i;
                
        
for (v[k]=1,ret+=min[k],i=0;i<n;i++)
            
if (!v[i]&&mat[k][i]<min[i])
                min[i]
=mat[k][i];
    
    }
    
int max=0;
    
for(int i=0;i<n;i++){ //找最大边权 
        if(max<min[i])max=min[i];
     }
     
return max;
    
//return ret;
}

int main()
{
   
// ifstream fcin("agrinet.in");
  
//  ofstream fcout("agrinet.out");
    int  i,j,k,sum=0,node;
    
int dist;
    
int cas;
    scanf(
"%d",&cas);
    
while( cas -- ){ 
           
         scanf(
"%d",&n);            
       
         memset( map,inf, 
sizeof(map));
         
         
for( i=0;i<n;i++)
          
for( j=0;j<n;j++){
            scanf(
"%d",&map[i][j]);
  
      }
   
         printf(
"%d\n",prim(n,map));
     }
//system("pause");
     
    
return 0;



posted on 2008-10-26 13:16 阅读(1207) 评论(0)  编辑 收藏 引用 所属分类: pku

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理