CF219D Choosing Capital for Treeland
2024-08-22 16:05:47
树形dp。
首先一个很常规的想法就是如果u到v有一条边,那么建立cost(u, v) = 0, cost(v, u) = 1的两条边.
可以两遍dfs。
先任选一个点作为根节点,第一遍从下往上dfs,维护节点u到他的所有子节点的距离,很容易得出dis[u] = ∑dis[v] + cost(u, v) (v为u的儿子节点)。
第二遍从上往下dfs,维护节点u到所有节点的距离,考虑u和他的一个儿子节点v,两者到所有节点的区别只有cost(u, v)这条边是不一样的,如果cost(u, v) = 1,那么dis2[v] = dis2[u] - 1,否则dis2[v] = dis2[u] + 1.
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 2e5 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int n;
vector<int> v[maxn];
vector<bool> c[maxn];
int dis[maxn];
bool vis[maxn]; void init()
{
for(int i = ; i <= n; ++i) v[i].clear(), c[i].clear();
Mem(dis, );
} void dfs1(int now)
{
vis[now] = ;
for(int i = ; i < (int)v[now].size(); ++i)
{
if(!vis[v[now][i]])
{
dis[now] += c[now][i];
dfs1(v[now][i]);
dis[now] += dis[v[now][i]];
}
}
}
void dfs2(int now)
{
vis[now] = ;
for(int i = ; i < (int)v[now].size(); ++i)
{
if(!vis[v[now][i]])
{
dis[v[now][i]] = dis[now] + (c[now][i] ? - : );
dfs2(v[now][i]);
}
}
} int main()
{
while(scanf("%d", &n) != EOF)
{
init();
for(int i = ; i < n; ++i)
{
int x = read(), y = read();
v[x].push_back(y); c[x].push_back();
v[y].push_back(x); c[y].push_back();
}
Mem(vis, ); dfs1();
Mem(vis, ); dfs2();
int Min = INF;
for(int i = ; i <= n; ++i) Min = min(Min, dis[i]);
write(Min); enter;
for(int i = ; i <= n; ++i) if(dis[i] == Min) write(i), space;
enter;
}
return ;
}
最新文章
- 如何在spring容器开始后,和销毁前,执行一些操作
- java.util.concurrent.RejectedExecutionException: Task java.util.concurrent.FutureTask@1f303192 rejected from java.util.concurrent.ThreadPoolExecutor@11f7cc04[Terminated, pool size = 0, active threads
- Android存储访问及目录
- Unity3D 材质球设置参数无效果的解决方法
- Unity3D 游戏计时功能实现
- Android概述
- C语言 段位
- php 系统命令执行函数
- mysql 基础命令入门学习
- Cocos2dx开发(4)——Windows环境创建Cocod2dx 3.2第一个项目HelloWorld
- Oracle merge into 使用记录
- VS Code - Debugger for Chrome
- c语言学习笔记 —— 数组
- obj-c编程15[Cocoa实例04]:基于Core Data的多文档程序示例[未完待续]
- 添加一个Activity
- [文摘]那些一心想要离开 BAT 的人,后来怎么样了?
- [UE4]添加射击的准心
- boost bind使用指南
- elasticsearch启动时提示内存不足错误的解决方法
- datagrid的toolbar的两种实现方式