tarjan + topo 40pts WA+RE求调

P3387 【模板】缩点

跟你犯了同样的错误,顺带帮你改改 - 拓扑```int v = adj[u][i];```改为adj2 - 拓扑```for(int i = 1;i <= n;i ++)```中n改为scccount ![](//图.tk/8) ```cpp #include <iostream> #include <queue> #include <stack> #include <vector> using namespace std; int n, m; int a[100005]; vector<int> adj[100005]; vector<int> adj2[100005]; stack<int> st; int pre[100005]; int low[100005]; int sccNo[100005]; int dscc[100005]; int dis[100005]; int ind[100005]; int scccount = 0; int dfsTime = 0; // 缩点 void tarjan(int u) { pre[u] = low[u] = ++dfsTime; st.push(u); for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if (!pre[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (!sccNo[v]) { low[u] = min(low[u], pre[v]); } } if (low[u] == pre[u]) { sccNo[u] = ++scccount; dscc[scccount] = a[u]; while (true) { if (st.empty()) break; if (st.top() == u) break; int f = st.top(); sccNo[f] = scccount; dscc[scccount] += a[f]; st.pop(); } st.pop(); } } void toposort() { queue<int> q; for (int i = 1; i <= scccount; i++) { if (ind[i] == 0) { dis[i] = dscc[i]; q.push(i); } } while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < (int)adj2[u].size(); i++) { int v = adj2[u][i]; dis[v] = max(dis[v], dis[u] + dscc[v]); ind[v]--; if (!ind[v]) q.push(v); } } } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; while (m--) { int u, v; cin >> u >> v; adj[u].push_back(v); } for (int i = 1; i <= n; i++) { if (!pre[i]) { dfsTime = 0; tarjan(i); } } for (int i = 1; i <= n; i++) { for (int j = 0; j < (int)adj[i].size(); j++) { int g = adj[i][j]; if (sccNo[i] != sccNo[g]) { adj2[sccNo[i]].push_back(sccNo[g]); ind[sccNo[g]]++; } } } // 变为有向无环图 toposort(); int ans = -10000000; for (int i = 1; i <= n; i++) { ans = max(ans, dis[i]); } cout << ans << endl; return 0; } ```
by Q__A__Q @ 2023-06-28 23:42:19


@[Patron_Saint](/user/635780) re是因为m的最大值为1e5,所以vector建图的时候要开1e5以上而不是和点的个数n一样
by Q__A__Q @ 2023-06-28 23:43:59


|