tyvj1940创世纪——贪心(基环树)

题目：http://www.joyoi.cn/problem/tyvj-1940

基环树的样子，看了书上的讲解，准备写树上DP，然后挂了：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int const MAXN=1e6+,inf=1e9;

int n,a[MAXN],f[MAXN][],head[MAXN],ct,s[MAXN],h,col[MAXN],cr,rt,ans;

int sta[MAXN],top,reg[MAXN];

bool in[MAXN],fl,vis[MAXN];

struct N{

    int to,next;

    N(int t=,int n=):to(t),next(n) {}

}edge[MAXN];

void add(int x,int y)

{

    edge[++ct]=N(y,head[x]);head[x]=ct;

    edge[++ct]=N(x,head[y]);head[y]=ct;

}

void ser(int x)

{

    col[x]=cr;

    for(int i=head[x],u;i;i=edge[i].next)

        if(!col[u=edge[i].to])ser(u);

}

void tj(int rt,int x)

{

    if(fl)return;

    sta[++top]=x;vis[x]=;

    for(int i=head[x],u;i;i=edge[i].next)

    {

        if(edge[i].to==a[x])continue;

        if(!vis[u=edge[i].to])tj(rt,u);

        else

        {

            while(sta[top]!=rt)

            {

                int t=sta[top];

                s[++h]=t;

                in[t]=;top--;

            }

            in[rt]=;s[++h]=rt;top--;

            fl=;return;

        }

    }

    top--;

}

void dfs(int x)

{

    int mn=inf,sum=;

    for(int i=head[x],u;i;i=edge[i].next)

    {

        u=edge[i].to;

        if(u==rt)continue;

        if(u==a[x]||col[u]!=col[x])continue;

        dfs(u);

        f[x][]+=max(f[u][],f[u][]);

        sum+=f[u][];

        mn=min(mn,f[u][]-f[u][]);

    }

    if(sum==)f[x][]=;

    else f[x][]=sum-mn;

}

void dfs2(int x)

{

    int mn=inf,sum=;

    for(int i=head[x],u;i;i=edge[i].next)

    {

        u=edge[i].to;

        if(u==rt)continue;

        if(u==a[x]||col[u]!=col[x])continue;

        dfs(u);

        f[x][]+=max(f[u][],f[u][]);

        sum+=f[u][];

        mn=min(mn,f[u][]-f[u][]);

    }

    if(sum==)f[x][]=;

    else if(x==a[rt])f[x][]=sum;

    else f[x][]=sum-mn;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        reg[i]++;reg[a[i]]++;

        add(i,a[i]);

    }

    for(int i=;i<=n;i++)

    {

        if(!col[i])h=,cr++,ser(i);

        int rt;fl=;int s=;

        for(int j=;j<=n;j++)

            if(reg[j]>&&col[j]==cr)

                {rt=j;break;}

        tj(rt,i);

        dfs(rt);

        s=max(f[rt][],f[rt][]);

        dfs2(rt);

        s=max(s,f[rt][]);

        ans+=s;

    }

    printf("%d",ans);

    return ;

}

无输出的冗长树上DP

题目挺有意思，自己本来也想过贪心的做法，但不会处理链与环交接处的问题，想不清楚一条链会对环有什么影响；

然后看了看别人的博客，才发现链对环没有影响。。。因为环上的点不论链上怎样，仍还有环上别的点限制它；

所以链与环都是隔一个选一个，贪心。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

queue<int>q;

int const MAXN=1e6+;

int n,a[MAXN],reg[MAXN],ans;

bool vis[MAXN],v2[MAXN];

void bfs()

{

    for(int i=;i<=n;i++)

        if(!reg[i])q.push(i);

    while(q.size())

    {

        int x=q.front();q.pop();

        vis[x]=;

        if(!vis[a[x]])

        {

            ans++;//因为多起点开始，不方便直接求链的长度，所以一个一个加

            vis[a[x]]=;

            reg[a[a[x]]]--;

            if(!reg[a[a[x]]]&&!vis[a[a[x]]])

                q.push(a[a[x]]);

        }

    }

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        reg[a[i]]++;

    }

    bfs();

    for(int i=;i<=n;i++)

        if(!vis[i]&&!v2[i])

        {

            int cnt=;v2[i]=;

            int j=a[i];

            while(!v2[j])cnt++,j=a[j];

            ans+=cnt/;

        }

    printf("%d",ans);

    return ;

}

巴特西

tyvj1940创世纪——贪心(基环树)

最新文章

热门文章