P1653 [USACO04DEC] Cow Ski Area G 题解

yyy_empty · 2023-07-19 19:11:48 · 题解

题目大意

在一张图中，对于一个点，有多条出边，指向与它相连的并且海拔小于等于它的点。求最少要添加多少条边使得整个图强联通。

思路

Tarjan 缩点。强连通图的概念是既可以通过有向边从 A 到 B，也可以通过有向边从 B 到 A，所以我们可以记录只有出边和只有入边的点取最大值（贪心思想，将这两种点两两配对）。

Code

//P1653 [USACO04DEC] Cow Ski Area G 
#include<bits/stdc++.h>

#define reg register

using namespace std;

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

const int N = 550;
const int xx[4]={-1,1,0,0};
const int yy[4]={0,0,-1,1};

int n,m,mmap[N][N],first[N*N],cnt,low[N*N],dfn[N*N],belong[N*N],in[N*N],out[N*N],tot,now;
int ans1,ans2;  //ans1 记录只有出边的点，ans2 记录只有入边的点 
stack<int>s;
bool instack[N*N];
struct edge{
    int to,nxt;
}edges[N*N*4];

int C(int i,int j) { return (i-1)*m+j; }  //将图中的坐标化成点，方便表示 

void add(int u,int v) {  //构图 
    edges[++cnt].to=v;
    edges[cnt].nxt=first[u];
    first[u]=cnt;
}

void dfs(int root) {  //缩点ing 
    dfn[root]=low[root]=++now;
    s.push(root);instack[root]=true;
    for (reg int t=first[root];t;t=edges[t].nxt) {
        int h=edges[t].to;
        if (!dfn[h]) dfs(h),low[root]=min(low[root],low[h]);
        else if (instack[h]) low[root]=min(low[root],low[h]);
    }
    if (low[root]==dfn[root]) {  //该点是强连通分量的源点(或者孤点) 
        tot++;
        while (1) {
            int h=s.top();s.pop();
            belong[h]=tot;instack[h]=false;
            if (h==root) break;
        }
    }
}

int main(){
    m=read();n=read();
    for (reg int i=1;i<=n;++i) {
        for (reg int j=1;j<=m;++j) mmap[i][j]=read();  
    }
    for (reg int i=1;i<=n;++i) {
        for (reg int j=1;j<=m;++j) {
            for (reg int f=0;f<4;++f) { 
                int to_x=i+xx[f],to_y=j+yy[f];
                if (to_x>=1&&to_x<=n&&to_y>=1&&to_y<=m&&mmap[i][j]>=mmap[to_x][to_y]) //满足条件，建边 
                    add(C(i,j),C(to_x,to_y));
            }
        }
    }
    for (reg int i=1;i<=n;++i) 
        for (reg int j=1;j<=m;++j) if (!dfn[C(i,j)]) dfs(C(i,j));  //防止有节点没有遍历到 
    for (reg int i=1;i<=n;++i) {
        for (reg int j=1;j<=m;++j) {
            int root=C(i,j);
            for (reg int t=first[root];t;t=edges[t].nxt) {
                int h=edges[t].to;
                if (belong[root]==belong[h]) continue;  //这条边属于一个强连通分量里面的内边 
                out[belong[root]]++;in[belong[h]]++;  //记录缩点之后每个节点的入度和出度 
            }
        }
    }
    if (tot==1) {   //特判 
        printf("0\n");
        return 0;
    }
    for (reg int i=1;i<=tot;++i) {  //统计数量 
        if (!in[i]) ans1++;
        if (!out[i]) ans2++; 
    }
    printf("%d\n",max(ans1,ans2));  //输出最大值 
    return 0;
}
//end