【P2016】战略游戏（贪心||树状DP）

这个题真是。。。看了一会之后，发现有一丝丝的熟悉，再仔细看了看，R，这不是那个将军令么。。。然后果断调出来那个题，还真是，而且貌似还是简化版的。。。于是就直接改了改建树和输入输出直接交了。。阿勒，就20分。。真是不给面子，于是就继续简化了代码。。。然后又交，变0分了。发现建树的时候双向边里面放了顺序一样的字母。。再改过来，A了，然而树形DP做法还未可知。。或许蒟蒻我就只能贪心吧。。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define re register

using namespace std;

struct po

{

    int next;

    int to;

    int dis;

};

po edge[];

int head[],b[],temp[],dis[],f[];

int T,s,t,n,m,x,w,a,l,num,flag,ans,visit[],k;

inline int read() {

    char ch=' ';

    int w=,x=;

    while(ch!='-'&&(ch<''||ch>''))ch=getchar();

    if(ch=='-')w=-,ch=getchar();

    while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

    return x*w;

}

inline void add_edge(int from,int to,int dis)

{

    edge[++num].next=head[from];

    edge[num].to=to;

    edge[num].dis=;

    head[from]=num;

}

inline void dfs(int x,int fa)

{

    temp[++l]=x;

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

    if(edge[i].to!=fa)

    dfs(edge[i].to,x);

}

int main()

{

    cin>>n;

    k=;

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

    {

        s=read();

        s++;

        m=read();

        for(re int j=;j<=m;j++)

        {

            t=read();

            t++;

            add_edge(s,t,);

            add_edge(t,s,);

            f[t]=s;

        }

    }

    dfs(,);

    for(re int i=n;i>=;i--)

    if(!b[temp[i]]&&!b[f[temp[i]]])

    b[f[temp[i]]]=;

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

    if(b[i])

    ans++;

    cout<<ans;

}

给出树状DP做法：

#include<iostream>

#include<cstdio>

#include<cstring>

#define re register

using namespace std;

struct po

{

    int next;

    int to;

    int dis;

};

po edge[];

int head[],b[],temp[],dis[],f[][];

int T,s,t,n,m,x,w,a,l,num,flag,ans=,visit[],k;

inline int read() {

    char ch=' ';

    int w=,x=;

    while(ch!='-'&&(ch<''||ch>''))ch=getchar();

    if(ch=='-')w=-,ch=getchar();

    while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

    return x*w;

}

inline void add_edge(int from,int to,int dis)

{

    edge[++num].next=head[from];

    edge[num].to=to;

    edge[num].dis=;

    head[from]=num;

}

inline void dfs(int x,int fa)

{

    f[x][]=;f[x][]=;

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

    {

        int u=edge[i].to;

        if(u!=fa)

        {

            dfs(u,x);

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

            f[x][]+=f[u][];

        }

    }

}

int main()

{

    cin>>n;

    k=;

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

    {

        s=read();

        s++;

        m=read();

        for(re int j=;j<=m;j++)

        {

            t=read();

            t++;

            add_edge(s,t,);

            add_edge(t,s,);

        }

    }

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

    {

        memset(f,,sizeof(f));

        dfs(i,i);

        ans=min(ans,min(f[i][],f[i][]));

    }

    cout<<ans;

}

巴特西

【P2016】战略游戏（贪心||树状DP）

最新文章

热门文章