[USACO3.1]最短网络 Agri-Net（并查集，最小生成树，排序）

巧妙的优化，观察代码两个循环是否可以联合到一个循环处理，还有本题的排序其实可以在输入的时候就直接处理了

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int mp[10000][10000];
int parent[1005],rank[1005];
struct node{
    int x,y,z;
}edge[10000];
//并查集路径优化 
int find(int x){
    if(x==parent[x])return x;return parent[x]=find(parent[x]);
}
//并查集秩优化 
void unio(int x,int y){
    int x_root=find(x);int y_root=find(y);if(x_root==y_root)return;if(x_root>y_root){
    parent[y_root]=x_root;}else{
    parent[x_root]=y_root;if(x_root==y_root){
    rank[y_root]++;}}
}
//插入排序 
void charu_sort(int x){
    node pp=edge[x];int k=x-1;while(pp.z<edge[k].z){
    edge[k+1]=edge[k];k--;}edge[k+1]=pp;
}
int main(){
    scanf("%d",&n);int k=0;for(int i=1;i<=n;i++){
    parent[i]=i;//初始化优化合并 for(int j=1;j<=n;j++){
    cin>>mp[i][j];if(j<i){
    if(mp[i][j]!=0){
    edge[k].x=i;edge[k].y=j;edge[k++].z=mp[i][j];}if(k>=2){
    charu_sort(k-1);//边输入边排序 }} }}//克鲁斯卡尔算法 long long count=0,sum=0;for(int i=0;i<k;i++){
    if(find(edge[i].x)!=find(edge[i].y)){
    unio(edge[i].x,edge[i].y);sum+=edge[i].z;count++;}if(count==n-1){
    break;}}printf("%lld",sum);return 0;
}