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;

}