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;
}