题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1040
题目链接:https://www.luogu.com.cn/problem/P2607
题目链接:https://loj.ac/problem/10162
做法
看似有向边,其实可以转化为无向边。
构成一个基环森林
但是需要特判一种情况:当有两个人互相讨厌的时候,形成一棵树,同时有重边(我的找环做法需要sort判重,可能有更好的方法)
然后把森林里的每一棵树或者基环树DP一下(就是没有上司的舞会模型,超水),把答案加起来
注意会爆int
做完了
代码
#include <iostream> #include <cstdio> #include <algorithm> #define Re register #define LL long long using namespace std; inline int read() { Re int x = 0; char ch = getchar(); while (!isdigit(ch)) ch = getchar(); while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar(); return x; } const int maxN = 1000005; struct Edge { int nxt, to; } e[maxN << 1]; struct EE { int u, v; } E[maxN]; int cnte = 1, head[maxN]; inline void add_Edge(int i, int j) { e[++cnte].nxt = head[i]; e[cnte].to = j; head[i] = cnte; } LL f[maxN][2]; int N, val[maxN], huan[maxN], cnt, a, b; bool vis[maxN], ishuan[maxN], flag; void dfs(int u, int fa) { vis[u] = true; for (Re int i = head[u]; i; i = e[i].nxt) { Re int v = e[i].to; if (v == fa) continue; if (vis[v]) { a = u, b = v; continue; } dfs(v, u); } } void DP(int u, int fa) { f[u][0] = 0, f[u][1] = val[u]; for (Re int i = head[u]; i; i = e[i].nxt) { Re int v = e[i].to; if (v == fa || (u == a && v == b) || (v == a && u == b)) continue; DP(v, u); f[u][0] += max(f[v][1], f[v][0]); f[u][1] += f[v][0]; } } LL Ans = 0; bool cmp(EE x, EE y) { if (x.u != y.u) return x.u < y.u; return x.v < y.v; } int main() { N = read(); for (Re int x, i = 1; i <= N; ++i) { val[i] = read(), x = read(); E[i].u = min(i, x), E[i].v = max(i, x); } sort(E + 1, E + N + 1, cmp); for (int i = 1; i <= N; ++i) { if (E[i].u == E[i - 1].u && E[i].v == E[i - 1].v) continue; add_Edge(E[i].u, E[i].v); add_Edge(E[i].v, E[i].u); } LL res = 0; for (int u = 1; u <= N; ++u) { if (vis[u]) continue; a = 0, b = 0, dfs(u, 0); if (!a || !b) { DP(u, 0); Ans += max(f[u][1], f[u][0]); continue; } res = 0; DP(a, b); res = max(res, f[a][0]); DP(b, a); res = max(res, f[b][0]); Ans += res; } printf("%lld\n", Ans); return 0; }