[USACO 2014 Gold] Ski Course Rating

作法：

如果有一格 P 的答案是 D ，那麼考慮所有滿足「存在一條從 P 走到他的路徑，使得路徑上兩相鄰點的點權差不超過D」的格子，這些格子在限制差為 D 的時候是兩兩互通的，並且我們知道這些點的總數 >= T （因為 P 的答案是 D），也就代表這些點的答案都會 <= D 。因此我們可以考慮先把格子們轉換成圖，並且對兩相鄰的點之間建邊，權重是點權差，然後按照邊權從小到大一條一條加入圖中，用 disjoint set 維護，當加入某條邊後有一個連通塊的大小超過 T 的話，代表這個連通塊中的所有數的答案都會是這條邊的權重。而題目要求的是總和，所以可以只對每個 disjoint set 只維護有幾個格子是詢問的格子即可，不用維護詢問的是哪些格子，而每個連通塊的大小是顯然一定要紀錄的。

code :

#include<bits/stdc++.h>
#define ABS(x) ((x)>0 ? (x) : (-(x)))
#define LL long long
using namespace std;
const int maxn=500+10 ;
 
int dx[]={1,0},dy[]={0,1} ;
 
int G[maxn][maxn] ;
struct P
{
    int x,y,val ;
    bool operator < (const P &rhs) const
    {
        return val==rhs.val ? (x==rhs.x ? y<rhs.y : x<rhs.x) : val<rhs.val ;
    }
}p[2*maxn*maxn];
 
int q[maxn*maxn] ;
int fa[maxn*maxn],size[maxn*maxn] ;
int getfa(int x)
{
    return fa[x]==x ? x : fa[x]=getfa(fa[x]) ;
}
 
main()
{
    freopen("skilevel.in","r",stdin) ;
    freopen("skilevel.out","w",stdout) ;
    int n,m,T ; scanf("%d%d%d",&n,&m,&T) ;
    if(T==1) { printf("0\n") ; return 0 ; }
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
        scanf("%d",&G[i][j]) ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
    {
        int x ; scanf("%d",&x) ;
        size[i*m+j]=1 ; fa[i*m+j]=i*m+j ;
        if(x==1) q[i*m+j]++ ;
    }
 
    int cnt=0 ;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++)
    {
        int x=m*i+j ;
        for(int z=0;z<2;z++)
        {
            int ni=i+dx[z] , nj=j+dy[z] ;
            if(ni<0||ni>=n||nj<0||nj>=m) continue ;
            int y=m*ni+nj ;
            p[cnt++]=(P){x,y,ABS(G[i][j]-G[ni][nj])} ;
        }
    }
 
    sort(p,p+cnt) ;
    LL ans=0LL ;
    for(int i=0;i<cnt;i++)
    {
        int x=getfa(p[i].x) , y=getfa(p[i].y) ;
        if(x==y) continue ;
        size[y]+=size[x] ; fa[x]=y ; q[y]+=q[x] ;
        if(size[y]>=T) ans+=(LL)q[y]*p[i].val, q[y]=0 ;
    }
    printf("%lld\n",ans) ;
}