题目大意:有\(n\)个士兵,每个士兵有\(d_i,a_i\),表示\(i\)和\(d_i\)士兵不能同时出征,\(i\)士兵战斗力为\(a_i\),组一个士兵集合使其战斗力最大。
基环树\(\mathcal{dp}\)。
每次找到一个环并强行断开,进行两次\(\mathcal{dp}\),\(\mathcal{dp}\)方法:
设\(dp_{i,0}\)为不选\(i\)的最大战斗力,\(dp_{i,1}\)为选\(i\)的最大战斗力。
\[dp_{i,0} = \sum_{v \in \texttt{son}} \max(dp_{v,0},dp_{v,1})\\ dp_{i,1} = \left(\sum_{v \in \texttt{son}} dp_{v,0}\right) + a_i\\ \]\(\texttt{dfs}\)既珂。
找环:
有向图:
迭代,每次判断\(f_x\)是否被访问过,如果访问过,说明\(x\)为环上一点,否则\(x \leftarrow f_x\)继续迭代。
int findcircle(int x)
{
vis[x] = 1;
while(!vis[f[x]]) x = f[x],vis[f[x]] = 1;
return x;
}
无向图:
拓扑排序,结束后度数\(\ge 2\)的节点为环上的点。
bool bfs(void)
{
queue <int> q;
int cnt = 0;
for(int i = 1; i <= n; i++) if(du[i] == 1) q.push(i);
while(!q.empty())
{
int head = q.front();q.pop();
cnt++;
for(int i = 0; i < g[head].size(); i++)
{
int v = g[head][i];
if(du[v])
{
if(--du[v] == 1) q.push(v);
}
}
}
return cnt == n; // 判断是否有环
}
这里是有向图,所以用第一个方法。先断\(x\),进行\(\mathcal{dp}\),再断\(f_x\),进行\(\mathcal{dp}\),取最大值相加(因为是森林)。
# include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5,inf = 0x3f3f3f3f;
int n;
vector <int> g[N];
int a[N],du[N];
long long dp[N][2]; // 0 not choose 1 choose
int h[N],htot;
bool vis[N];
int f[N];
int rt;
long long ans;
void DP(int x)
{
vis[x] = 1;
dp[x][0] = 0,dp[x][1] = 1ll * a[x];
for(int i = 0; i < g[x].size(); i++)
{
int v = g[x][i];
if(v != rt)
{
DP(v);
dp[x][1] += dp[v][0];
dp[x][0] += max(dp[v][0],dp[v][1]);
}
else dp[v][1] = -inf; //强制不选
}
return;
}
void find_circle(int x)
{
vis[x] = 1;
while(!vis[f[x]]) x = f[x],vis[x] = 1;
rt = x;
// printf("rt = %d\n",rt);
// for(int i = 1; i <= n; i++) dp[i][0] = 0,dp[i][1] = a[i];
DP(rt);
long long dpx0 = dp[x][0],dpx1 = dp[x][1];
x = f[x];
rt = x;
// for(int i = 1; i <= n; i++) dp[i][0] = 0,dp[i][1] = a[i];
DP(rt);
long long _dpx0 = dp[x][0],_dpx1 = dp[x][1];
ans += max(max(dpx0,_dpx1),max(dpx1,_dpx0));
return;
}
int main(void)
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
int v;
scanf("%d%d",&a[i],&v);
f[i] = v;
g[v].push_back(i);
}
for(int i = 1; i <= n; i++)
{
if(!vis[i])
{
find_circle(i);
}
}
printf("%lld\n",ans);
return 0;
}