CodeForces - 219D Choosing Capital for Treeland(树形dp)
2021-06-05 08:06
阅读:516
标签:bit scanf font sizeof using ++ set api namespace
题目大意:
给一个n节点的有向无环图,要找一个这样的点,该点到其它n-1要逆转的道路最少;
题解思路:
建边时正边赋值0,反边赋值1;及遍历全图后总权值最小。
跑树形dp; 可以从一个结点可以从fa son得到值;
2遍dfs;
#includeusing namespace std; #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f const int maxn=4e5+10; struct edge{ int u,v,w,next; }e[maxn]; int g[maxn],tot=0; int dp[maxn][2],vis[maxn]; void creat_edge(int u,int v,int w) { e[++tot]=(edge){u,v,w,g[u]}; g[u]=tot; } void dfs(int u) { vis[u]=1; for(int i=g[u];i>0;i=e[i].next) { int v=e[i].v,w=e[i].w; if(vis[v]) continue; dfs(v); dp[u][0]+=dp[v][0]+w; } } void dfs1(int u) { vis[u]=1; for(int i=g[u];i>0;i=e[i].next) { int v=e[i].v,w=e[i].w; if(vis[v]) continue; dp[v][1]+=dp[u][1]+dp[u][0]-dp[v][0]-w+(w?0:1); dfs1(v); } dp[u][1]+=dp[u][0]; } int main() { int n; scanf("%d",&n); for(int i=1;i ) { int u,v; scanf("%d%d",&u,&v); creat_edge(u,v,0); creat_edge(v,u,1); } mem(vis,0); dfs(1); mem(vis,0); dfs1(1); int ans=inf; // for(int i=1;i// { // cout// }cout// // for(int i=1;i// { // cout// }cout for(int i=1;i) { if(dp[i][1]ans) ans=dp[i][1]; } coutendl; int f=1; for(int i=1;i) { if(dp[i][1]==ans) { if(!f) cout" "; couti; f=0; } } return 0; }
CodeForces - 219D Choosing Capital for Treeland(树形dp)
标签:bit scanf font sizeof using ++ set api namespace
原文地址:https://www.cnblogs.com/minun/p/10807766.html
文章来自:搜素材网的编程语言模块,转载请注明文章出处。
文章标题:CodeForces - 219D Choosing Capital for Treeland(树形dp)
文章链接:http://soscw.com/index.php/essay/90792.html
文章标题:CodeForces - 219D Choosing Capital for Treeland(树形dp)
文章链接:http://soscw.com/index.php/essay/90792.html
评论
亲,登录后才可以留言!