P1653题解

· · 题解

题目解读

原题传送门

一句话，求最少加多少条边使此无向图只有一个强连通分量。

建图应该不难想到，每个点连一条有向边到比自己低或相等高的点。

相等高？！说明这一些点可以互相联通，这么说把他们看成一个点，因为无论缆车装在哪个点上，都能达到相同的效果。恕我语文表达太烂，举个例子吧。

最终答案就是缩完点后入度为 0 的点和出度为 0 的点个数的最大值。

当然只有一个强连通分量是要特判 0。

AC Code

#include<bits/stdc++.h>
#include<vector>
#include<stack>
using namespace std;
const int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
const int N=250005; 
int W,L,h[505][505];
int ID(int x,int y){
    return (x-1)*L+y;
}
vector <int> E[N];
int dfn[N],low[N],col[N],colnum,dfnum;
bool ins[N],in[N],out[N];
stack <int> S;
void Tarjan(int u){
    dfn[u]=low[u]=++dfnum;
    S.push(u);ins[u]=true;
    for(int i=0;i<E[u].size();i++){
        int v=E[u][i];
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[v],low[u]);
        }else if(ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        col[u]=++colnum;
        ins[u]=false;
        while(S.top()!=u){
            col[S.top()]=colnum;
            ins[S.top()]=false;
            S.pop();
        }
        S.pop();
    }
}
int main(){
    scanf("%d%d",&L,&W);
    for(int i=1;i<=W;i++)
        for(int j=1;j<=L;j++)
            scanf("%d",&h[i][j]);
    for(int i=1;i<=W;i++)
        for(int j=1;j<=L;j++)
            for(int k=0;k<4;k++){
                int xx=dir[k][0]+i,yy=dir[k][1]+j;
                if(xx<1||xx>W||yy<1||yy>L) continue;
                if(h[i][j]>=h[xx][yy]) E[ID(i,j)].push_back(ID(xx,yy));
            }
    for(int i=1;i<=W*L;i++) if(!dfn[i]) Tarjan(i);
    for(int i=1;i<=W*L;i++)
        for(int j=0;j<E[i].size();j++)
            if(col[i]!=col[E[i][j]])
                in[col[E[i][j]]]=out[col[i]]=true;
    int ans1=0,ans2=0;
    for(int i=1;i<=colnum;i++){
        if(!in[i]) ans1++;
        if(!out[i]) ans2++;
    }
    if(colnum==1) printf("0\n");
    else printf("%d\n",max(ans1,ans2));
    return 0;
}