NC106972 Cow Ski Area

NC106972 Cow Ski Area

一、题目

\(N*M\)的滑雪场，每个点都有他的高度，滑雪的时候只能向四周相邻的不高于当前点的高度的点滑，现在滑雪场准备修建若干个缆车线路，使得奶牛可以从任意一个点运动到滑雪场的每个点，问最少需要建多少条缆车线路。

二、题解

本质还是有向图，通过加边使其强连通。
相邻而且高度大于等于的关系建单向边，然后就是上一个题了—— \(tarjan\)缩点，统计入度和出度为零的点的个数。

\(Code\)

#include <stdio.h>
#include <iostream>
#include <map>
#include <algorithm>
#include <queue>
#include <string>
#include <cstring>
#include <vector>

// C++可以AC，G++直接挂掉
using namespace std;
const int MAXN = 550;                  // 原来矩阵的长宽最大值
const int N = MAXN * MAXN, M = N << 2; // 新建图的点个数，及边个数，此题的边比较多 普通的N<<1不够
int g[MAXN][MAXN];                     // 原始地势高低的矩阵

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// Tarjan算法求强连通分量
int dfn[N], low[N], ts;
int stk[N], top;
int in_stk[N];
int id[N], scc_cnt;
int din[N], dout[N];
void tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    stk[++top] = u;
    in_stk[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int x;
        do {
            x = stk[top--];
            in_stk[x] = 0;
            id[x] = scc_cnt;
        } while (x != u);
    }
}

int n, m; // 行数与列数

int main() {
#ifndef ONLINE_JUDGE
    freopen("NC106972.in", "r", stdin);
#endif
    memset(h, -1, sizeof h); // 初始化链式前向星
    scanf("%d %d", &m, &n);  // 败家的东西，先输入m后输入n

    // 输入原始数据矩阵
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &g[i][j]);

    // 根据题意，向四边探索建图,建图用的点号计算办法(x-1)*m+y
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= m; y++) {
            int id = (x - 1) * m + y;
            if (x > 1 && g[x][y] >= g[x - 1][y]) add(id, id - m); // 上一行
            if (x < n && g[x][y] >= g[x + 1][y]) add(id, id + m); // 下一行
            if (y > 1 && g[x][y] >= g[x][y - 1]) add(id, id - 1); // 左一列
            if (y < m && g[x][y] >= g[x][y + 1]) add(id, id + 1); // 右一列
        }

    // 注意点的个数为n*m
    for (int i = 1; i <= n * m; i++)
        if (!dfn[i]) tarjan(i);

    // 遍历每条出边，看看此边的两个端点是不是在同一个连通分量中，如果不是，标识两个连通分量间的出度入度变化
    for (int u = 1; u <= n * m; u++) {
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            int a = id[u], b = id[v];
            if (a != b)
                dout[a]++, din[b]++;
        }
    }
    // 统计所有连通分量入度、出度为零的个数
    // 将出度入度为零的强连通分量间建边，可以最少代价完成强连通补边
    int a = 0, b = 0;
    for (int i = 1; i <= scc_cnt; i++) {
        if (!din[i]) a++;
        if (!dout[i]) b++;
    }
    if (scc_cnt == 1) // 特判一个强连通分量的特殊情况
        printf("0\n");
    else
        printf("%d\n", max(a, b)); // 输出两者最大值
    return 0;
}