BZOJ1040/ZJOI2008/骑士

Posted on By 二价氢

这一类题(图)的特征,就是树上有环,环上接树,由数学知识我们可以知道,五元环和六元环比较稳定,如1,3,5-环己三烯这类东西……然后三元环四元环啥的就不太稳定,想想就知道,如果树上没有环的话,这题就是裸的树状DP,这很容易理解,那么我们就可以将环看成一个节点,然后先在这个节点内作环形DP,然后再把环丢到树中作树状DP

AC-Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
using namespace std;
const int MAXN=1000005,MAXM=2000005;
typedef long long PType;
//--邻接表
int Next[MAXM],Pfirst[MAXN],Target[MAXM],TotEdge;
void AddEdge(int s,int t)
{
    TotEdge++;
    Target[TotEdge]=t;Next[TotEdge]=Pfirst[s];Pfirst[s]=TotEdge;
}
//--题目
int N;
int tP;
PType tV,UV[MAXN];
//--读入
void Read()
{
    scanf("%d",&N);
    for (int i=1;i<=N;i++)
    {
        scanf("%lld%d",&UV[i],&tP);
        AddEdge(i,tP);AddEdge(tP,i);
    }
}
//--遍历图->找环 Tarjan Tarjan Tarjan Tarjan......
int dfn[MAXN],low[MAXN],father[MAXN],num;
PType F[MAXN][2];
void DFS(int x)
{
    dfn[x]=low[x]=++num;
    F[x][0]=0;F[x][1]=UV[x];
    for (int i=Pfirst[x];i;i=Next[i])
    {
        int q=Target[i];
        if (!dfn[q])
        {
            father[q]=x;
            DFS(q);
            low[x]=min(low[x],low[q]);
            if (dfn[x]<low[q])
            {
                F[x][0]=F[x][0]+max(F[q][0],F[q][1]);
                F[x][1]=F[x][1]+F[q][0];
            }
        }else if (dfn[q]<dfn[x]&&q!=father[x])
        {
            low[x]=min(low[x],dfn[q]);
        }
    }
    for (int i=Pfirst[x];i;i=Next[i])
    {
        if (father[Target[i]]!=x&&dfn[x]<dfn[Target[i]])
        {
            int q=Target[i];
            pair<PType,PType> Pow;
            Pow=make_pair(F[q][0],F[q][1]);
            for (int j=father[q];j!=x;j=father[j])
                Pow=make_pair(max(Pow.first,Pow.second)+F[j][0],Pow.first+F[j][1]);
            F[x][0]=F[x][0]+max(Pow.first,Pow.second);
            Pow=make_pair(F[q][0],-10000000000000LL);//<- -INF
            for (int j=father[q];j!=x;j=father[j])
                Pow=make_pair(max(Pow.first,Pow.second)+F[j][0],Pow.first+F[j][1]);
            F[x][1]=F[x][1]+Pow.first;
        }
    }
}
void Work()
{
    PType ans=0;
    for (int i=1;i<=N;i++)
    {
        if (!dfn[i])
        {
            DFS(i);
            ans=ans+max(F[i][0],F[i][1]);
        }
    }
    printf("%lld\n",ans);
}
int main()
{
    Read();
    Work();
    return 0;
}

QAQ今天给Ubuntu系统装驱动然后显卡成功罢工了2333