傳送門
顧名思義，模板awa

#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <string> #include <queue> #include <vector> #define ll long long using namespace std; const int M = 300500; const int N = 30050; int n, m; int tot = 0, a, b, tim = 0, top = 0; int sum[N], col[N], dfs[N], low[N], zhan[N], v[N]; struct node {int to, nxt; } p[M]; int cnt = -1, fi[N]; void addline(int x, int y) {p[++cnt] = (node){ y, fi[x] };fi[x] = cnt; } void tarjan(int x) {dfs[x] = low[x] = ++tim;zhan[++top] = x;for (int i = fi[x]; ~i; i = p[i].nxt) {int v = p[i].to;if (dfs[v] == 0) {tarjan(v);low[x] = min(low[x], low[v]);} else if (col[v] == 0)low[x] = min(low[x], low[v]);}if (low[x] == dfs[x]) {col[x] = ++tot;sum[tot] = v[x];while (zhan[top] != x) {col[zhan[top]] = tot;sum[tot] += v[zhan[top--]];}top--;}return; } int dp[N], ru[N]; void topu() {queue<int> q;for (int i = n + 1; i <= tot; i++) {if (ru[i] == 0)q.push(i);}while (!q.empty()) {int now = q.front();q.pop();dp[now] = max(dp[now], sum[now]);for (int i = fi[now]; ~i; i = p[i].nxt) {int v = p[i].to;dp[v] = max(dp[v], dp[now] + sum[v]);ru[v]--;if (ru[v] == 0)q.push(v);}} } int main() {scanf("%d%d", &n, &m);tot = n; //以后的縮點編號從m+1開始for (int i = 1; i <= 3 * n; i++) fi[i] = -1;for (int i = 1; i <= n; i++) {scanf("%d", &v[i]);}for (int i = 1; i <= m; i++) {scanf("%d%d", &a, &b);addline(a, b);}for (int i = 1; i <= n; i++) {if (dfs[i] == 0)tarjan(i);}for (int i = 1; i <= n; i++) {for (int j = fi[i]; ~j; j = p[j].nxt) {int u = p[j].to;if (col[i] != col[u]) {addline(col[i], col[u]);ru[col[u]]++;}}}topu();int ans = 0;for (int i = n + 1; i <= tot; i++) {ans = max(ans, dp[i]);}printf("%d\n", ans);return 0; } /* 1 3 3 3 3 3 3 3 3 3 3 */

總結

以上是生活随笔為你收集整理的强连通分量：洛谷P3387 模板：缩点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。