FZU 2233 ~APTX4869 贪心+并查集

分析：http://blog.csdn.net/chenzhenyu123456/article/details/51308460

#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long LL;
typedef pair<int,int>pii;
const int N=8e2+5;
const int INF=0x3f3f3f3f;
struct Node{
  int u,v,w;
  bool operator<(const Node &rhs)const{
    return w<rhs.w;
  }
}p[N*N];
int tot,n,w,fa[N];
int find(int x){
  return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
    while(~scanf("%d",&n)){
        tot=0;
     for(int i=1;i<=n;++i){
      fa[i]=i;
      for(int j=1;j<=n;++j){
        scanf("%d",&w);
        if(i<j){++tot,p[tot].u=i,p[tot].v=j,p[tot].w=w;}
      }
    }
      sort(p+1,p+1+tot);
      int ans=0;
      for(int i=1;i<=tot;++i){
        int u=find(p[i].u),v=find(p[i].v);
        if(u!=v){
          fa[u]=v;
          ans=p[i].w;
        }
      }
      printf("%d
",ans);
    }
    return 0;
}