题意：给定无向连通图和起点S，每个点有权值，求遍历无向图得到的最大权值和。但是不能走回头路，即如果从U走到V那么下一步不可以从V走到U。
分析：将图分成两种组成，一种是环，一种是链。对于S所在的环，肯定可以遍历这个环回到S。对于其他的环，肯定可以走到这个环中，遍历这个环，然后原路返回。那么最优解就是首先遍历所有的环，连接这些环的链也可以被遍历到，然后选择一条最大的链走到尽头。
#include <bits/stdc++.h> #define mp make_pair #define mst(a,n) memset(a, n, sizeof(a)) #define debug(x) cout << #x << ": " << x << endl #define pb push_back typedef long long LL; const int maxn = 2e5 + 10; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; using namespace std; int f[maxn], n, m, u, v, cnt[maxn], s, fa[maxn], vis[maxn], dep[maxn]; LL w[maxn], dp[maxn], ans = -1; vector<int> g[maxn]; int find(int x) { return f[x] == -1 ? x : f[x] = find(f[x]); } void dfs(int now, int pre) { vis[now] = true; dep[now] = dep[pre] + 1; for (int i = 0; i < g[now].size(); ++i) { int to = g[now][i]; if (to == pre) continue; if (!vis[to]) { fa[to] = now; dfs(to, now); } else if (dep[to] <= dep[now]) { cnt[to]++; cnt[now]--; } } } void _dfs(int now) { for (int i = 0; i < g[now].size(); ++i) { int to = g[now][i]; if (fa[to] == now) { _dfs(to); cnt[now] += cnt[to]; } } } bool __dfs(int now) { bool flg = false; for (int i = 0; i < g[now].size(); ++i) { int to = g[now][i]; if (fa[to] == now) { if (__dfs(to)) { flg = true; int fu = find(now), fv = find(to); if (fu != fv) { dp[fu] += dp[fv]; f[fv] = fu; } } } } return flg || cnt[now] != 0; } void ___dfs(int now, LL sum) { ans = max(ans, sum); for (int i = 0; i < g[now].size(); ++i) { int to = g[now][i]; if (fa[to] == now) { if (find(to) != s) ___dfs(to, sum + w[to]); else ___dfs(to, sum); } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; ++i) { f[i] = -1; cnt[i] = 0; vis[i] = 0; cin >> w[i]; dp[i] = w[i]; } for (int i = 1; i <= m; ++i) { cin >> u >> v; g[u].pb(v); g[v].pb(u); } cin >> s; dfs(s, 0); _dfs(s); __dfs(s); ___dfs(s, 0); cout << dp[s] + ans << endl; }
原文：https://www.cnblogs.com/smallhester/p/11551473.html
