P1653

billtun · 2023-08-20 22:56:58 · 题解

题目传送门

看懂题目后，就会发现这就是一道 Tarjan 的模板题。

首先是连边，当一个点（记为 a）的高度大于等于周围相邻的点（上下左右共四个，记为 b）时，就连一条从 a 到 b 的边。

然后跑一遍 Tarjan。再遍历每一个强连通分量，如果他的出度为 0， ans1 加一；如果他的入度为 0，ans2 加一。

最后，输出 ans1 与 ans2 的最大值。

因为一个强连通分量里面的任意两个点都是可以互相滑到的，如果一个强连通分量入度为 0，即没有任何一个点可以滑到那里，就要建一条缆车；同理，如果一个强连通分量出度为 0，他也需要一条缆车到别的点去。

Code:

#include<bits/stdc++.h>
#define N 250005

using namespace std;

int n, m, h[505][505]={0};
vector<int> v[N];
int dfn[N], low[N], dfncnt=0;
int scc[N], sc=0, st[N], top=0;
int in[N]={0}, out[N]={0};
bool is_st[N];
int ans1=0, ans2=0;

void add(int x, int y){
    if(x>1 && h[x][y]>=h[x-1][y]) v[(x-1)*m+y].push_back((x-2)*m+y);
    if(x<n && h[x][y]>=h[x+1][y]) v[(x-1)*m+y].push_back(x*m+y);
    if(y>1 && h[x][y]>=h[x][y-1]) v[(x-1)*m+y].push_back((x-1)*m+y-1);
    if(y<m && h[x][y]>=h[x][y+1]) v[(x-1)*m+y].push_back((x-1)*m+y+1);
}

void Tarjan(int x){
    dfn[x]=low[x]=++dfncnt;
    st[++top]=x, is_st[x]=1;

    for(int i=0;i<(int)v[x].size();i++){
        int tmp=v[x][i];
        if(!dfn[tmp]) Tarjan(tmp), low[x]=min(low[x], low[tmp]);
        else if(is_st[tmp]) low[x]=min(low[x], dfn[tmp]);
    }

    if(dfn[x]==low[x]){
        sc++;
        while(st[top]!=x){
            scc[st[top]]=sc;
            is_st[st[top]]=0;
            top--;
        }
        scc[st[top]]=sc;
        is_st[st[top]]=0;
        top--;
    }
}

int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>h[i][j];
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            add(i, j);
        }
    }

    for(int i=1;i<=n*m;i++){
        if(!dfn[i]){
            Tarjan(i);
        }
    }

    for(int i=1;i<=n*m;i++){
        for(int j=0;j<(int)v[i].size();j++){
            int tmp=v[i][j];
            if(scc[i]!=scc[tmp]){
                in[scc[tmp]]++, out[scc[i]]++;
            }
        }
    }

    for(int i=1;i<=sc;i++){
        if(!in[i]) ans1++;
        if(!out[i]) ans2++;
    }

    if(sc==1) cout<<0;
    else cout<<max(ans1, ans2);
    return 0;
}