P2607

· · 个人记录

[ZJOI2008]骑士

空间被卡了？？？

N=1e6，然后开了大概有 20 个 long long 的数组。。。

然后被迫把部分非必要的 long long 改成了 bool，勉强跑过最后一个数据。

看来以后开数组还是要小心一点。

然后就是基环树，再加上一个 没有上司的舞会。

我们知道，如果建无向边可以很清楚的明白是一颗基环树，但是不好处理。

那么建有向边有不是基环树的可能吗？完全没有，甚至森林里的每棵树都是一颗基环树。

这里为了 DP，我们需要建立一颗外向树，即每个点有且仅有一条入边。

然后用 Tarjan 找 SCC，就是树中的环，从环的某位置开始 DP，并为了防止指向这个位置的点做了错误的转移，我们打上标记，并分类进行 DP。

然后就没了，那个转移方程和 P1352 没有区别。

f_i,_0=\sum\max\{f_v,_1,f_v,_0\} f_i,_1=\sum f_v,_0

没了。

时间复杂度 O(n+m)。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;

const ll N=1e6;

ll n,v,ans,cnt,num,top,flgloop,tot;

int ver[N+5],nxt[N+5],head[N+5],w[N+5];

int dfn[N+5],low[N+5],stk[N+5],c[N+5];

ll f1[N+5][2],f2[N+5][2];

bool vis1[N+5][2],vis2[N+5][2],ins[N+5];

vector<int> scc[N+5];

void tarjan(ll x) {
    dfn[x]=low[x]=++num;
    stk[++top]=x;ins[x]=1;
    for(ll i=head[x];i;i=nxt[i]) {
        if(!dfn[ver[i]]) {
            tarjan(ver[i]);low[x]=min(low[x],low[ver[i]]);
        }
        else {
            if(ins[ver[i]]) low[x]=min(low[x],dfn[ver[i]]);
        }
    }
    if(dfn[x]==low[x]) {
        cnt++;
        do {
            ins[stk[top]]=0;
            c[stk[top]]=cnt;
            scc[cnt].push_back(stk[top]);
        } while(x!=stk[top--]);
        if(scc[cnt].size()>1) flgloop=cnt;
    }
}

ll dp1(ll p,ll s) {
    if(vis1[p][s]) return f1[p][s];
    vis1[p][s]=1;
    if(s==1) f1[p][s]+=w[p];
    for(ll i=head[p];i;i=nxt[i]) {
        if(ver[i]==scc[flgloop][0]&&s==0) continue;
        if(ver[i]==scc[flgloop][0]&&s==1) return f1[p][s]=0;
        if(s==1) f1[p][s]+=dp1(ver[i],0);
        else f1[p][s]+=max(dp1(ver[i],0),dp1(ver[i],1));
    }
    return f1[p][s];
}

ll dp2(ll p,ll s) {
    if(vis2[p][s]) return f2[p][s];
    vis2[p][s]=1;
    if(s==1) f2[p][s]+=w[p];
    for(ll i=head[p];i;i=nxt[i]) {
        if(ver[i]==scc[flgloop][0]) continue;
        if(s==1) f2[p][s]+=dp2(ver[i],0);
        else f2[p][s]+=max(dp2(ver[i],0),dp2(ver[i],1));
    }
    return f2[p][s];
}

void add(ll u,ll v) {
    ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    n=read();

    for(ll i=1;i<=n;i++) {
        w[i]=read();v=read();add(v,i);
    }

    for(ll i=1;i<=n;i++) {
        if(dfn[i]) continue;
        flgloop=0;tarjan(i);
        if(!flgloop) continue;
        ans+=max(dp1(scc[flgloop][0],1),dp2(scc[flgloop][0],0));
    //  printf("scc[flgloop][0]=%lld dp1=%lld dp2=%lld\n",scc[flgloop][0],dp1(scc[flgloop][0],1),dp2(scc[flgloop][0],0));
    }

    write(ans);

    return 0;
}