题解 P3073 【[USACO13FEB]Tractor S】

daihang · 2020-03-01 22:16:03 · 题解

并查集+最小生成树算法

题目要求最大值最小化，满足最小生成树的性质

Details

1. 建图。除边缘外的每个点均可以向上下左右四个方向连边，点的编号可表示为: n*(i-1)+j (i为行,j为列)

实现代码：

int ex(int i,int j){
    return (i-1)*n+j;
}

边的权值即为两点高度差的绝对值

2. 如何维护集合的大小。初始化将size全设为1，后续再进行合并操作(merge)时，将旧的集合的大小更新到新的集合上。在新的集合大小大于(n*n)/2时，输出当前边的权值即可。

实现代码：

x=find(x);//find函数是为了找父亲
y=find(y);
if(x!=y){
    fa[x]=y;
    siz[y]+=siz[x];
    if(siz[y]>=(n*n+1)/2){
        cout<<w<<endl;
        return 0;
    }
}

3. 最小生成树Kruskal 不解释

不会的可以找模板题P3366 【模板】最小生成树

最后送上代码，祝各位水题切题愉快

#include<bits/stdc++.h>
using namespace std;
const int maxn=501;
int n;
int mp[maxn][maxn];
inline int read(){//快读
    int x=0,y=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')y=-y; ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*y;
}
int fa[maxn*maxn];
int siz[maxn*maxn];
struct node{
    int u,v,w;
    node(){}
    node(int uu,int vv,int ww){
        u=uu;
        v=vv;
        w=ww;
    }
}edge[maxn*maxn*4];
bool cmp(const node &a,const node &b){
    return a.w<b.w;
}
int ans=0;
void init(){
    for(int i=1;i<=n*n;i++){
        fa[i]=i;
        siz[i]=1;
    }
}
int find(int x){
    if(x==fa[x]) return x;
    else return fa[x]=find(fa[x]);
}
int ex(int i,int j){
    return (i-1)*n+j;
}
int main(){
    n=read();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            mp[i][j]=read();
        }
    }
    init();
    int tp=1;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(i>1){
                edge[tp]=node(ex(i,j),ex(i-1,j),abs(mp[i-1][j]-mp[i][j]));
                tp++;
            }
            if(j>1){
                edge[tp]=node(ex(i,j),ex(i,j-1),abs(mp[i][j-1]-mp[i][j]));
                tp++;
            }
            if(i<n){
                edge[tp]=node(ex(i,j),ex(i+1,j),abs(mp[i+1][j]-mp[i][j]));
                tp++;
            }
            if(j<n){
                edge[tp]=node(ex(i,j),ex(i,j+1),abs(mp[i][j+1]-mp[i][j]));
                tp++;
            }
        }
    }
    sort(edge+1,edge+tp,cmp);
    for(int i=1;i<tp;i++){
        int x=edge[i].u;
        int y=edge[i].v;
        int w=edge[i].w;
        x=find(x);
        y=find(y);
        if(x!=y){
            fa[x]=y;
            siz[y]+=siz[x];
            if(siz[y]>=(n*n+1)/2){
                cout<<w<<endl;
                return 0;
            }
        }
    }
}

写题解不易，求个赞