P1653题解

· · 题解

一道很不错的 tarjan 题目。

题目大意：

给定一个 n \times m 的矩阵，每个格子都与上下左右相联通，但只有高度大于时才可以走。因此可以加一些边直接连接一些格子，不考虑高度。现在为了使整个矩阵联通，最少加几条边？

思路：

看到矩阵，难道非得用矩阵吗？2 维转 1 维呀！

洛谷上还有 2 维转 1 维的题目，比如 P3073，不错的并查集题。

实现很简单，可以走的连一条边就行了。

然后就是套用非常经典的 tarjan 模板。不会 tarjan 的先去做 这题。

最后统计答案的时候，要先求出每个连通块的入度和出度。如果入度或者出度为 0，那么显然这个连通块与其他的需要有边相连。最后输出的很显然是入度为 0 和出度为 0 的最大值。

当然有一种特殊情况，只有一个连通块，就直接输出 0。

以上就是本题的思路，下面就看代码吧！

切勿抄袭！！！

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 250005//2维转1维,所以数组大小为500*500
inline int read() {//快读，没啥好说的
    int a=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9') {
        if  (c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        a=a*10+(c-'0');
        c=getchar();
    }
    return f*a;
}
int dfn[N],low[N],col[N],vis[N],vis1[N];//tarjan所需数组
int cl,k;
stack<int>s;
int head[N],cnt;//链式前向星数组
struct edge {
    int to,next;
} edge[N*4];//记得开四倍空间哦(上下左右)
void addedge(int a,int b) {
    edge[++cnt].to=b;
    edge[cnt].next=head[a];
    head[a]=cnt;
}
int n,m,a[505][505],ru[N],chu[N],ans1,ans2;//ans1表示入度为0，ans2表示出度为0
void dfs(int u) {//tarjan标程
    dfn[u]=low[u]=++k;
    s.push(u);
    vis[u]=1;
    vis1[u]=1;
    for (int i=head[u]; i; i=edge[i].next) {
        int v=edge[i].to;
        if (vis[v]==0) {
            dfs(v);
            low[u]=min(low[u],low[v]);
        } else if(vis1[v]==1)
            low[u]=min(low[u],low[v]);
    }
    if (dfn[u]==low[u]) {
        cl++;
        while(s.top()!=u) {
            int q=s.top();
            vis1[q]=-1;
            s.pop();
            col[q]=cl;//记录连通块编号 
        }
        s.pop();
        col[u]=cl;
        vis1[u]=-1;
    }
}
void jb(int a1,int b1,int a2,int b2) {//建边,a1b1、a2b2均表示坐标
    if(a2>n||a2<1||b2>m||b2<1)return;//如果点出界了，返回
    if(a[a1][b1]<a[a2][b2])return;//如果去不了，返回
    addedge((a1-1)*m+b1,(a2-1)*m+b2);//否则建边
   //这里用点的编号建边，即在此矩阵中排第几个
}
int main() {
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    m=read(),n=read();
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            a[i][j]=read();
    for(int i=1; i<=n; i++)//2维转1维
        for(int j=1; j<=m; j++) {
            jb(i,j,i+1,j);//上
            jb(i,j,i-1,j);//下 
            jb(i,j,i,j-1);//左
            jb(i,j,i,j+1);//右
        }
    n*=m;//点的编号为1-n*m
    for (int i=1; i<=n; i++)//tarjan
        if (vis[i]==0)
            dfs(i);
    if(cl==1){//这是一种特殊情况，只有一个连通块，那么不需要另外加边
        printf("0");
        return 0;
    }
    for(int i=1; i<=n; i++)
        for(int j=head[i]; j; j=edge[j].next) {
            int u=edge[j].to;
            if(col[i]!=col[u]) {
                ru[col[u]]++;//统计连通块的入度和出度
                chu[col[i]]++;
            }
        }
    for(int i=1; i<=cl; i++) {//统计入度出度为0的个数
        if(ru[i]==0)ans1++;
        if(chu[i]==0)ans2++;
    }
    printf("%d",max(ans1,ans2));//最后输出
    return 0;
}

总结：

这题要能想到 2 维转 1 维，并且要考虑全面，还是很好做的。

完结~