善良な王(最小生成木変形)

質問C:善良な王
時間制限:1 Secメモリ制限:128 MB
コミット:112解決:48
[コミット][ステータス][ディスカッション]
タイトルの説明
むかしむかし、貧しい国がありました.この国には善良で民を愛する王がいました.そこで彼はもともと豊かではない税金の中から一部のお金を出して、これらの村に道路を修理しようとしたが、国力が限られていて、すべての道路を修復することができず、王は村の2つの間に着くことを保証することにした.今、王は彼が建てる道の中で最も長いのが少なくともどれくらい長いか知りたいと思っています.
入力
複数組の試験データを入力し、各組の試験データはまず1つのnを入力し、n個の村が3<=n<=500であり、番号が1-nであることを示し、次に下のn*nの行列、i行目j列目の値、番号iから番号jの村までの距離がこの値であることを示し、単位1~65536
しゅつりょく
王が建てる道路の中で最も長い最小の長さを出力します.
サンプル入力
3
0 990 692
990 0 179
692 179 0
サンプル出力
692
ヒント

//  ：     ：
//    ：
//         ，           ；               。
//    ：           ，           （       ）
//          （      ）         ，  ，       ；
//                cmp           ，
//                       ;
#include
#include
#include
using namespace std;
#define M 0xfffff
int map[520][520];
int per[520];
int n;
struct node{
	int s;
	int e;
	int len;
}ans[25200];
void init()
{
	int i;
	for(i=1;i<=n;i++)
	  per[i]=i;
}
int cmp(node x,node y)
{
	return x.len>y.len;
}
int find(int a)
{
   int r=a;
   while(r!=per[r])
     r=per[r];
   return r; 
}
bool link (int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx!=fy)
	{
		per[fx]=fy;
		return true;
	}
  return false;
}
int main()
{
	int i,j,k,num,cnt,maxl;
	while(scanf("%d",&n)!=EOF)
	{
		k=0;
		memset(map,0,sizeof(map));
		memset(ans,0,sizeof(ans));
		init();
		for(i=1;i<=n;i++)
		  for(j=1;j<=n;j++)
		  {
		  	scanf("%d",&map[i][j]);
		  	if(map[i][j]>0)
		  	{
		  		ans[k].s=i;
		  		ans[k].e=j;
		  		ans[k].len=map[i][j];
		  		k++;
			  }
		  }
		  sort(ans,ans+k,cmp);
		  maxl=M;
		  for(i=0;ians[i].len)
		  		  maxl=ans[i].len;
			  }	
		  }
	 printf("%d
",maxl);
	}
	return 0;
}