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;
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhibbigg
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22 -
excel打印预览压线压字怎么办
PHP中文网 06-22