题解 P1653 [USACO04DEC] Cow Ski Area G

· · 题解

相关内容： Tarjan 缩点

一道不错的 Tarjan 缩点的题目。

分析

由于奶牛能向相邻的的方格之间滑雪，并且不能从低到高滑，这就有了建图的限制条件，需要判断能否满足将一个点与相邻的点建边。

建好图之后套上 Tarjan 缩点的板子，统计一下缩点之后每个点的出度和入度。

显然，我们需要将出度为 0 的点和入度为 0 的点之间建缆车，为了保证任意的点之间都能互通，建的缆车数量应该等于缩点后出度为 0 的点的个数和入度为 0 的点的个数的最大值。

注意

如果缩点后只有一个点，那么就不需要建缆车，这种情况需要特判。

#include<iostream>
#include<cstdio>

using namespace std;

const int N=5e5+10,M=5e6+10;

struct Edge{
    int next,to;
}edge[M];

int n,m,num,head[N],g[550][550],in[N],out[N];
int dfn[N],low[N],st[N],scc[N],siz[N],top,cnt,idx;
bool ins[N];

void add(int u,int v){
    edge[++num].next=head[u];
    edge[num].to=v;
    head[u]=num;
}

void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    ins[st[++top]=u]=true;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        int v;idx++;
        do{
            v=st[top--];
            ins[v]=false;
            scc[v]=idx;
        }while(u!=v);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&g[i][j]);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(i>1&&g[i-1][j]<=g[i][j])
                add((i-1)*n+j,(i-2)*n+j);
            if(i<m&&g[i+1][j]<=g[i][j])
                add((i-1)*n+j,i*n+j);
            if(j>1&&g[i][j-1]<=g[i][j])
                add((i-1)*n+j,(i-1)*n+j-1);
            if(j<n&&g[i][j+1]<=g[i][j])
                add((i-1)*n+j,(i-1)*n+j+1);
        }
    }
    int tot=n*m;
    for(int i=1;i<=tot;i++){
        if(!dfn[i])tarjan(i);
    }
    if(idx==1){
        printf("0");return 0;
    }
    for(int u=1;u<=tot;u++){
        for(int i=head[u];i;i=edge[i].next){
            int v=edge[i].to;
            if(scc[u]!=scc[v])
                out[scc[u]]++,in[scc[v]]++;
        }
    }
    int sum1=0,sum2=0;
    for(int i=1;i<=idx;i++){
        if(!out[i])sum1++;
        if(!in[i])sum2++;
    }
    printf("%d",max(sum1,sum2));
    return 0;
}