本文主要是介绍POJ 2375 Cow Ski Area（强连通），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
POJ 2375 Cow Ski Area
题目链接
题意：给定一个滑雪场，每个点能向周围4个点高度小于等于这个点的点滑，现在要建电缆，使得任意两点都有路径互相可达，问最少需要几条电缆
思路：强连通缩点，每个点就是一个点，能走的建边，缩点后找入度出度为0的个数的最大值就是答案，注意一开始就强连通了答案应该是0
代码：
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;const int N = 250005;
const int M = 1000005;
const int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};int n, m;struct Edge {int u, v;Edge() {}Edge(int u, int v) {this->u = u; this->v = v;}
} edge[M];int en, first[N], next[M];void add(int u, int v) {edge[en] = Edge(u, v);next[en] = first[u];first[u] = en++;
}int h[505][505];
int pre[N], dfn[N], sccn, sccno[N], dfs_clock;
stack<int> S;void dfs_scc(int u) {pre[u] = dfn[u] = ++dfs_clock;S.push(u);for (int i = first[u]; i + 1; i = next[i]) {int v = edge[i].v;if (!pre[v]) {dfs_scc(v);dfn[u] = min(dfn[u], dfn[v]);} else if (!sccno[v]) dfn[u] = min(dfn[u], pre[v]);}if (dfn[u] == pre[u]) {sccn++;while (1) {int x = S.top(); S.pop();sccno[x] = sccn;if (x == u) break;}}
}void find_scc() {sccn = dfs_clock = 0;memset(pre, 0, sizeof(pre));memset(sccno, 0, sizeof(sccno));for (int i = 0; i < n * m; i++)if (!pre[i]) dfs_scc(i);
}int in[N], out[N];int main() {while (~scanf("%d%d", &m, &n)) {en = 0;memset(first, -1, sizeof(first));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++)scanf("%d", &h[i][j]);}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int k = 0; k < 4; k++) {int x = i + d[k][0];int y = j + d[k][1];if (x < 0 || x >= n || y < 0 || y >= m) continue;if (h[i][j] >= h[x][y]) add(i * m + j, x * m + y);}}}find_scc();if (sccn == 1) {printf("0\n");continue;}memset(in, 0, sizeof(in));memset(out, 0, sizeof(out));for (int u = 0; u < n * m; u++) {for (int j = first[u]; j + 1; j = next[j]) {int v = edge[j].v;if (sccno[u] != sccno[v]) {in[sccno[v]]++;out[sccno[u]]++;}}}int ins = 0, outs = 0;for (int i = 1; i <= sccn; i++) {if (!in[i]) ins++;if (!out[i]) outs++;}printf("%d\n", max(ins, outs));}return 0;
}这篇关于POJ 2375 Cow Ski Area（强连通）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
