题解 P4955 【[USACO14JAN]Cross Country Skiing S】

· · 题解

一道水题

思路：

看了一下数据范围，直接二分+dfs可过

二分从0到11亿左右，亲测从1开始挂掉

dfs时不要回溯，直接标记，最后用check函数判断，如果这个点是关键点，且它没有被访问过，返回false。如果所有的都访问过，返回true。

注意事项：

  1. 二分记录答案当check函数返回true时更新为mid，不要记录为l或r。不但是这道题，二分都要这么做。

  2. 判断难度值是大于等于而不是大于。

时间复杂度为O(nm)，绝不可能炸掉。

代码：

#include<bits/stdc++.h>

#define int long long

using namespace std;

int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

struct node{
    int x;
    int y;
}e[50010];

int n,m;
int maps[1010][1010];
int ans;
int l,r,mid;
int cnt;
int sx,sy;
int fx[4][2] = {1,0,-1,0,0,1,0,-1};
bool bk[1010][1010];
bool bkk[1010][1010];

void dfs(int x,int y){
    //cout<<"x = "<<x<<" y = "<<y<<endl;
    for(int i = 0;i <= 3;i ++){
        int xx = x + fx[i][0];
        int yy = y + fx[i][1];
        //cout<<"xx = "<<xx<<" yy = "<<yy<<endl;
        if(xx >= 1 && yy >= 1 && xx <= n && yy <= m && !bk[xx][yy]){
            if(abs(maps[xx][yy] - maps[x][y]) <= mid){
                bk[xx][yy] = true;
                dfs(xx,yy);
            }
        }
    }
}

bool check(){
    memset(bk,false,sizeof(bk));
    bk[sx][sy] = true;
    dfs(sx,sy);
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            if(bkk[i][j]){
                if(!bk[i][j])return false;
            }
        }
    }
    return true;
}

signed main(){
    cin>>n>>m;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            maps[i][j] = read();
        }
    }
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            int xx;
            xx = read();
            if(xx == 1){
                bkk[i][j] = true;
                sx = i;
                sy = j;
            }
        }
    }
    l = 0,r = 2100000000;
    while(l <= r){
        mid = (l + r) / 2;
        if(check())r = mid - 1,ans = mid;
        else l = mid + 1;
    }
    cout<<ans;
    return 0;
}

实话说，感觉没有绿题难度。

以此纪念考场上的一道水题