M_sea

洛谷2607 [ZJOI2008]骑士
LuoguBZOJ分析基环树最大独立集。断掉环上任意一条边,强制某个端点不选即可。可能有多颗基环树,要累加。代码/...
扫描右侧二维码阅读全文
17
2019/01

洛谷2607 [ZJOI2008]骑士

Luogu

BZOJ

分析

基环树最大独立集。

断掉环上任意一条边,强制某个端点不选即可。

可能有多颗基环树,要累加。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

template<typename T>
inline void chkmax(T& x,T y) { if (y>x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

struct Edge { int v,nxt; };
Edge e[N<<1];
int head[N],cnt=2;

inline void addEdge(int u,int v) {
    e[cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt++;
}

int root[N];
inline void init(int n) { for (re int i=1;i<=n;++i) root[i]=i; }
inline int find(int x) { return x==root[x]?x:root[x]=find(root[x]); }
inline void merge(int u,int v) { u=find(u),v=find(v); if (u!=v) root[u]=v; }

int n,L;
int w[N];
ll f[N][2];

inline void dfs(int u,int fa) {
    f[u][0]=0,f[u][1]=w[u];
    for (re int i=head[u];i;i=e[i].nxt) {
        if (i==L||i==(L^1)) continue;
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u);
        f[u][0]+=max(f[v][0],f[v][1]);
        f[u][1]+=f[v][0];
    }
}

int cl[N],tot=0;

int main() {
    n=read(); init(n+1);
    for (re int i=1;i<=n;++i) {
        w[i]=read(); int x=read();
        addEdge(i,x); addEdge(x,i);
        if (find(i)!=find(x)) merge(x,i);
        else cl[++tot]=cnt-1;
    }
    ll ans=0;
    for (re int i=1;i<=tot;++i) {
        ll tmp=0; L=cl[i];
        dfs(e[cl[i]].v,0); chkmax(tmp,f[e[cl[i]].v][0]);
        dfs(e[cl[i]^1].v,0); chkmax(tmp,f[e[cl[i]^1].v][0]);
        ans+=tmp;
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 06 : 38 PM

1 条评论

  1. smy

    orz

发表评论