HDU 1827 Summer Holiday（强连通）

本文主要是介绍HDU 1827 Summer Holiday（强连通），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

HDU 1827 Summer Holiday

题目链接

题意：中文题

思路：强连通缩点，每个点的权值为强连通中最小值，然后入度为0的点就是答案

代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;const int N = 1005;
const int INF = 0x3f3f3f3f;int n, m, val[N];
vector<int> g[N];
int pre[N], lowlink[N], dfs_clock, sccno[N], scc_cnt, scc_val[N];
stack<int> S;void dfs(int u) {pre[u] = lowlink[u] = ++dfs_clock;S.push(u);for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];if (!pre[v]) {dfs(v);lowlink[u] = min(lowlink[u], lowlink[v]);} else if (!sccno[v]) lowlink[u] = min(lowlink[u], pre[v]);}if (pre[u] == lowlink[u]) {scc_cnt++;scc_val[scc_cnt] = INF;while (1) {int x = S.top(); S.pop();scc_val[scc_cnt] = min(scc_val[scc_cnt], val[x]);sccno[x] = scc_cnt;if (x == u) break;}}
}void find_scc() {dfs_clock = scc_cnt = 0;memset(pre, 0, sizeof(pre));memset(sccno, 0, sizeof(sccno));for (int i = 1; i <= n; i++)if (!pre[i]) dfs(i);
}int in[N];int main() {while (~scanf("%d%d", &n, &m)) {for (int i = 1; i <= n; i++) {g[i].clear();scanf("%d", &val[i]);}int u, v;while (m--) {scanf("%d%d", &u, &v);g[u].push_back(v);}find_scc();memset(in, 0, sizeof(in));for (int u = 1; u <= n; u++) {for (int j = 0; j < g[u].size(); j++) {int v = g[u][j];if (sccno[u] != sccno[v])in[sccno[v]]++;}}int ans = 0, cnt = 0;for (int i = 1; i <= scc_cnt; i++)if (!in[i]) {ans += scc_val[i];cnt++;}printf("%d %d\n", cnt, ans);}return 0;
}

这篇关于HDU 1827 Summer Holiday（强连通）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---