D. Choosing Capital for Treeland

题意

给出一颗有方向的n个节点的树，现在要选择一个点作为首都。

问最少需要翻转多少条边，使得首都可以到所有其他的城市去，以及相应的首都可以是哪些点。

思路

先忽略掉树中的方向，dp[i]表示i节点到它的子树所有点最少需要翻转的边。

进行第一遍dfs

如果u-v的方向是u-->v，那么dp[u]=dp[u]+dp[v];，否则dp[u]=dp[u]+dp[v]+1;，表示u-v这条边要翻转。

这时根节点的dp值就是根节点作为首都需要翻转的边，进行第二遍dfs：

dp[i]表示i作为首都需要翻转的最少边的数量

如果u-v的方向是u-->v，那么dp[v]=dp[u]+1;，否则dp[v]=dp[u]-1。

代码

#include<bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;

const int N=1e6+10;

const int mod=1e9+7;

const int inf=0x3f3f3f3f;

vector<int>vec[N],ans;

int n,dp[N];

map<int,map<int,int> >mp;

void dfs(int u,int fa)

{

    for(int v:vec[u])

    {

        if(v==fa) continue;

        dfs(v,u);

        dp[u]+=(dp[v]+!mp[u][v]);

    }

}

void dfs2(int u,int fa)

{

    for(int v:vec[u])

    {

        if(v==fa) continue;

        if(mp[u][v]) dp[v]=dp[u]+1;

        else dp[v]=dp[u]-1;

        dfs2(v,u);

    }

}

int main()

{

    scanf("%d",&n);

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

    {

        int u,v;

        scanf("%d%d",&u,&v);

        mp[u][v]=1;//mp[u][v]==1,表示u-v的方向是u-->v

        vec[u].pb(v);

        vec[v].pb(u);

    }

    dfs(1,0);

    dfs2(1,0);

    int maxn=inf;

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

    {

        if(dp[i]<maxn)

        {

            maxn=dp[i];

            ans.clear();

            ans.pb(i);

        }

        else if(dp[i]==maxn)

            ans.pb(i);

    }

    printf("%d\n",maxn);

    for(int v:ans)

        printf("%d ",v);

    printf("\n");

    return 0;

}

巴特西

CF#135 D. Choosing Capital for Treeland 树形DP

D. Choosing Capital for Treeland

题意

思路

代码

最新文章

热门文章