Codeforce 219D(树形dp)

本文主要是介绍Codeforce 219D(树形dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：点击打开链接

题意：由n各节点组成的有向树，要求选一个点作为首都，通过反转一些边使得任何一个点都能到达首都，输出反转的最少次数和可能成为首都的节点编号

代码：

#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int SIZE=200005;
const int INF=0x3f3f3f3f;
int dp[SIZE],num[SIZE],used[SIZE];
struct node{int to,cost;
};
vector<node> G[SIZE];
void dfs1(int s,int sum){int i,tmp;dp[1]+=sum;used[s]=1;for(i=0;i<G[s].size();i++){tmp=G[s][i].to;if(G[tmp].size()&&!used[tmp]){dfs1(tmp,G[s][i].cost);}}
}                                               //以1为根节点，通过根节点到其他节点的
void dfs2(int s){                               //路径和推出其他节点的路径和int i,tmp;used[s]=1;for(i=0;i<G[s].size();i++){tmp=G[s][i].to;if(!used[tmp]){if(G[s][i].cost==0)                 //根据父节点推出子节点dp[tmp]=dp[s]+1;elsedp[tmp]=dp[s]-1;dfs2(tmp);}}
}
int main(){                                     //就是将正向边设为1，反向边设为0int n,i,j,a,b,ans;                          //求哪一个节点到其他的路径和最小while(scanf("%d",&n)!=EOF){ans=INF;for(i=1;i<=n;i++)G[i].clear();memset(dp,0,sizeof(dp));memset(used,0,sizeof(used));for(i=0;i<n-1;i++){scanf("%d%d",&a,&b);G[b].push_back((node){a,1});G[a].push_back((node){b,0});}                                       //建树dfs1(1,0);memset(used,0,sizeof(used));dfs2(1);for(i=1;i<=n;i++)ans=min(ans,dp[i]);                     //找出最小值printf("%d\n",ans);for(i=1;i<=n;i++)if(dp[i]==ans)printf("%d ",i);printf("\n");}return 0;
}

 

这篇关于Codeforce 219D(树形dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---