洛谷 3073 [USACO13FEB]Tractor S 题解

发表于 | 阅读次数：
本文字数： 756 字 | 阅读时长 ≈ 4 分钟

题意简述

给定一个 $n\times n$ 的矩阵 $a$，两个相邻的格子之间的代价，就是两个格子 $a$ 值之差的绝对值。请你找到一个联通块，使得它格子数超过 $\lfloor \dfrac{n^2}{2} \rfloor$ ，并且最大的边权最小。

$n\le 1000$，$a_{i,j}\le 10^6$，对于所有$1\le i,j\le n$

思路框架

比较基础的问题，首先“最大值最小”想到二分，然后对于相邻的两个格子，如果 $a$ 值之差的绝对值 $<=mid$ ，就用并查集合并起来这两个点，最后找并查集里有没有 $size>\lfloor \dfrac{n^2}{2} \rfloor$ 的联通块即珂。

注意：并查集是一维的结构，把二维压缩到一维的方法：$(i,j)\rightarrow (i-1)n+j$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

#include <bits/stdc++.h>using namespace std;
namespace Flandre_Scarlet
{
        #define N 1333
        #define F(i,l,r) for(int i=l;i<=r;++i)
        #define D(i,r,l) for(int i=r;i>=l;--i)
        #define Fs(i,l,r,c) for(int i=l;i<=r;c)
        #define Ds(i,r,l,c) for(int i=r;i>=l;c)
        #define MEM(x,a) memset(x,a,sizeof(x))
        #define FK(x) MEM(x,0)
        #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
        #define p_b push_back
        #define sz(a) ((int)a.size())
        #define iter(a,p) (a.begin()+p)
        void R1(int &x)
        {
            x=0;char c=getchar();int f=1;
            while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
            while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
            x=(f==1)?x:-x;
        }
        void Rd(int cnt,...)
        {
            va_list args;
            va_start(args,cnt);
            F(i,1,cnt) 
            {
                int* x=va_arg(args,int*);R1(*x);
            }
            va_end(args);
        }
        class DSU
        {
        public:
                int Fa[N*N],Cnt[N*N];
                void Init(int n){F(i,1,min(n,N*N-1)) Fa[i]=i,Cnt[i]=1;}
                // 一定要注意这里是N*N
                // 我在这里都写的N，然后挂了...
                int  Find(int x){return x==Fa[x]?x:Fa[x]=Find(Fa[x]);}
                bool Merge(int u,int v)
                {
                        int au=Find(u),av=Find(v);
                        if (au==av) return false;
                        if (Cnt[au]<Cnt[av]) Cnt[av]+=Cnt[au],Fa[au]=av;
                        else                                   Cnt[au]+=Cnt[av],Fa[av]=au;
                        return true;
                }
        }D;

        int n,a[N][N];
        void Input()
        {
                R1(n);
                F(i,1,n) F(j,1,n) R1(a[i][j]);
        }

        #define id(i,j) ((i-1)*n+j) //二维转化成一维
        int dx[2]={1,0},dy[2]={0,1}; 
        //为了避免重复枚举，每个点只考虑它正下，正右方的点
        bool cxk(int x)
        {
                D.Init(n*n);
                F(i,1,n) F(j,1,n) F(k,0,1)
                {
                        int nx=i+dx[k],ny=j+dy[k];
                        if (nx<=n and ny<=n and abs(a[i][j]-a[nx][ny])<=x) 
                        //在矩阵内 并且 a值差的绝对值<=mid
                        {
                                D.Merge(id(i,j),id(nx,ny));
                                //合并这两个点
                        }
                }
                int Max=-1;
                F(i,1,n*n) Max=max(Max,D.Cnt[D.Find(i)]);
                return Max>=n*n/2;
        }
        void Soviet()
        {
                int l=0,r=2e6;
                while(l<r)
                {
                        int mid=(l+r)>>1;
                        if (cxk(mid)) r=mid;
                        else l=mid+1;
                }
                printf("%d\n",l);
        }

        #define Flan void
        Flan IsMyWife()
        {
                Input();
                Soviet();
        }
}
int main(){
        Flandre_Scarlet::IsMyWife();
        getchar();getchar();
        return 0;
}
w