骑士

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 3293 字
每个骑士恨另一个骑士，恨人者不可同队，求军团
一本通
练习
正文

/*
原题：骑士（一本通 5.2 练习5）
题意：每个骑士恨另一个骑士，恨人者不可同队，求军团最大战斗力（基环树最大独立集）。
思路：每人恰恨一人，构成基环树森林。对每个连通块：剥出环，环上挂的树做树形 DP 得 dp_in；再在环上做“相邻不可同选”的环形 DP（分首点选/不选两情况）。
复杂度：O(N) 时间，O(N) 空间。
易错点：冲突边恰为环边，环上 DP 要同时处理首尾冲突；战斗力累加用 long long。
*/
#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
vector<int> g[N];
int w[N],hate[N];
int indeg[N];
bool oncycle[N];
int dp0[N],dp1[N];
int din0[N],din1[N];
bool vis[N];
long long total=0;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>hate[i];
        g[i].push_back(hate[i]);
        g[hate[i]].push_back(i);
        indeg[hate[i]]++;
    }
    queue<int> q;
    for(int i=1;i<=n;i++)
        if(indeg[i]==0)q.push(i);
    while(!q.empty()){
        int u=q.front();q.pop();
        int v=hate[u];
        indeg[v]--;
        if(indeg[v]==0)q.push(v);
    }
    for(int i=1;i<=n;i++)
        if(indeg[i]>0)oncycle[i]=true;
    for(int i=1;i<=n;i++){
        if(oncycle[i]&&!vis[i]){
            vector<int> comp;
            queue<int> bq;
            bq.push(i);
            vis[i]=true;
            comp.push_back(i);
            vector<int> parent(n+1,-1);
            while(!bq.empty()){
                int u=bq.front();bq.pop();
                for(int v:g[u])
                    if(!vis[v]){
                        vis[v]=true;
                        parent[v]=u;
                        comp.push_back(v);
                        bq.push(v);
                    }
            }
            vector<int> order=comp;
            reverse(order.begin(),order.end());
            for(int u:order){
                if(oncycle[u])continue;
                dp0[u]=0;
                dp1[u]=w[u];
                for(int v:g[u])
                    if(v!=parent[u]&&!oncycle[v]){
                        dp0[u]+=max(dp0[v],dp1[v]);
                        dp1[u]+=dp0[v];
                    }
            }
            for(int u:order){
                if(!oncycle[u])continue;
                long long s1=w[u],s0=0;
                for(int v:g[u])
                    if(v!=parent[u]&&!oncycle[v]){
                        s1+=dp0[v];
                        s0+=max(dp0[v],dp1[v]);
                    }
                din0[u]=s0;
                din1[u]=s1;
            }
            vector<int> cyc;
            int cur=i;
            do{
                cyc.push_back(cur);
                cur=hate[cur];
            }while(cur!=i);
            int k=cyc.size();
            vector<long long> a(k),b(k);
            for(int t=0;t<k;t++){
                a[t]=din1[cyc[t]];
                b[t]=din0[cyc[t]];
            }
            vector<long long> f0a(k),f1a(k);
            f0a[0]=-1;
            f1a[0]=a[0];
            for(int t=1;t<k;t++){
                f0a[t]=max(f0a[t-1],f1a[t-1])+b[t];
                f1a[t]=f0a[t-1]+a[t];
            }
            long long bestA=f0a[k-1];
            vector<long long> f0b(k),f1b(k);
            f0b[0]=b[0];
            f1b[0]=-1;
            for(int t=1;t<k;t++){
                f0b[t]=max(f0b[t-1],f1b[t-1])+b[t];
                f1b[t]=f0b[t-1]+a[t];
            }
            long long bestB=max(f0b[k-1],f1b[k-1]);
            total+=max(bestA,bestB);
        }
    }
    cout<<total<<"\n";
    return 0;
}
骑士

正文

一本通·提高篇的其它内容
