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
爬 阅读(1226)
评论(0) 编辑 收藏 引用 所属分类:
pku