傳送門
題意：給定無向連通圖和起點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; }
codeforces登錄。?
