POJ-2485 Highways + POJ-1258 Agri-Net 【Kruskal】

都是纯板子题

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<cstdlib>
//#include<windows.h>
#define first fi
#define second se
using namespace std;
typedef long long ll;
const int N = 1e6+10;
const int INF = 0x3f3f3f3f;
const int inf = - INF;
const int mod = 1e9+7;
const double pi = acos(-1.0);
int n,m;
int father[505];
void init(){
    m=0;
    memset(father,-1,sizeof(father));
}
struct node {
    int u,v,w;
    node(){}
    node(int u,int v, int w):u(u),v(v),w(w){}
    bool operator < (const node &rhs)const{
        return w < rhs.w;
    }
}edge[N]; 
int Find(int x){
    return father[x]==-1?x:father[x]=Find(father[x]);
}
int Kruskal(){
    int maxn=-1;
    int cnt=0;
    for(int i=0;i<m;i++){
        int u=edge[i].u;
        int v=edge[i].v;
        if(Find(u)!=Find(v)){
            father[Find(u)]=Find(v);
            maxn=max(maxn,edge[i].w);
            if(++cnt>=n-1) return maxn;  
        }
    }
    return -1;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        init();
        int t;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                scanf("%d",&t);
                edge[m++]=node(i,j,t);
            }
        }
        sort(edge,edge+m);
        printf("%d\n",Kruskal());
    }
    //system("pause");
    return 0;
}

1258可以直接用2485改改就交，注意要多组输入。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<cstdlib>
#include<windows.h>
#define first fi
#define second se
using namespace std;
typedef long long ll;
const int N = 1e6+10;
const int INF = 0x3f3f3f3f;
const int inf = - INF;
const int mod = 1e9+7;
const double pi = acos(-1.0);
ll n,m;
ll father[505];
void init(){
    m=0;
    memset(father,-1,sizeof(father));
}
struct node {
    ll u,v,w;
    node(){}
    node(ll u,ll v, ll w):u(u),v(v),w(w){}
    bool operator < (const node &rhs)const{
        return w < rhs.w;
    }
}edge[N]; 
ll Find(int x){
    return father[x]==-1?x:father[x]=Find(father[x]);
}
ll Kruskal(){
    ll sum=0;
    ll cnt=0;
    for(ll i=0;i<m;i++){
        ll u=edge[i].u;
        ll v=edge[i].v;
        if(Find(u)!=Find(v)){
            father[Find(u)]=Find(v);
            sum+=edge[i].w;
            if(++cnt>=n-1) return sum;  
        }
    }
    return -1;
}
int main(){
    //int T;
    //scanf("%d",&T);
    while(~scanf("%lld",&n)){//注意多组输入
        init();
        ll t;
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=n;j++){
                scanf("%lld",&t);
                edge[m++]=node(i,j,t);
            }
        }
        sort(edge,edge+m);
        printf("%d\n",Kruskal());
    }
    system("pause");
    return 0;
}