正題

---

題目大意

每個(gè)騎士有一個(gè)不可以同時(shí)上場(chǎng)的騎士，和一個(gè)戰(zhàn)斗力。求最大戰(zhàn)斗力。

---

解題思路

類似沒有上司的舞會(huì)
其實(shí)就是在基環(huán)樹森林，我們可以利用二次樹形dp的方法。
先找到環(huán)，然后強(qiáng)行將環(huán)斷開進(jìn)行一次dp，然后強(qiáng)行連上進(jìn)行一次dp，兩次答案求最大值。

---

code

#include<cstdio> #include<algorithm> #include<cstring> #define ll long long #define N 1000010 using namespace std; struct node{ll to,next; }a[N]; ll w[N],n,x,ans,tot,fa[N],root,f[N],g[N],ls[N],d[N],mark; bool v[N]; void addl(ll x,ll y)//連邊 {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void check_c(ll x)//找環(huán) {v[x]=true;if(v[d[x]]) mark=x;else check_c(d[x]);return; } void dp(ll x)//樹形dp {v[x]=true;f[x]=w[x];g[x]=0;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y!=mark)//如果是斷開就不選{dp(y);g[x]+=max(f[y],g[y]);f[x]+=g[y];}else f[y]=-2147483647/3;}return; } int main() {scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld%lld",&w[i],&d[i]),addl(d[i],i);for(ll i=1;i<=n;i++){if(v[i]) continue;check_c(i);dp(mark);ll maxs=max(f[mark],g[mark]);mark=d[mark];root=0;dp(mark);ans+=max(maxs,max(f[mark],g[mark]));}printf("%lld",ans); }

總結(jié)

以上是生活随笔為你收集整理的P2607-[ZJOI2008]骑士【基环树,树形dp】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。