当前位置:网站首页>codeforces Valera and Elections (这思维题是做不明白了)
codeforces Valera and Elections (这思维题是做不明白了)
2022-08-09 06:36:00 【先求一个导】
题目
题意: 给定一棵以1为根的树,有的边坏了。选择尽量少的点,这些点可以修复其到1的路径上坏的边。
思路: dfs。如果某个叶子对应的边恰好是坏的,那必定修复。之后我想的是从这里回溯到点1,把对应的边修好。但是时间复杂度高而且比较难实现。所以可以拿一个变量维护某个点对应的子树中是否存在点被选择过,这样即使他头上的边是坏的,也不会额外计数,而某个点对应子树中没有点被选过,他也是必选的。这种带返回值的dfs写的比较少,着实菜。
时间复杂度: O(n)
代码:
// Problem: C. Valera and Elections
// Contest: Codeforces - Codeforces Round #216 (Div. 2)
// URL: https://codeforces.com/problemset/problem/369/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,k,T;
struct node{
int v,op;
bool operator<(const node&rhs)
{
return op > rhs.op;
}
};
vector<node> va[N];
int ans;
vector<int> res;
int dfs(int cur,int fa,int last) //上一条边
{
bool t = 0; //是否有节点被选
bool leaf = 1;
for(auto tmp:va[cur])
{
int j = tmp.v;
if(j==fa) continue; leaf = 0;
int op = tmp.op;
t |= dfs(j,cur,op);
}
// cout<<cur<<" "<<fa<<":"<<t<<endl;
if(leaf&&last==2)
{
res.push_back(cur); return true;}
if(!t && last==2) {
res.push_back(cur); t = true;} //没有孩子选
return t;
}
void solve()
{
cin>>n;
for(int i=0;i<n-1;++i)
{
int x,y,op; cin>>x>>y>>op;
va[x].push_back({
y,op}),va[y].push_back({
x,op});
}
// for(int i=1;i<=n;++i) sort(va[i].begin(),va[i].end());
dfs(1,0,1);
cout<<res.size()<<"\n";
for(int i=0;i<res.size();++i)
{
if(i) cout<<" ";
cout<<res[i];
}
}
signed main(void)
{
solve();
return 0;
}
边栏推荐
猜你喜欢
05 多线程与高并发 - ThreadPoolExecutor 源码解析
报错:FSADeprecationWarning: SQLALCHEMY_TRACK_MODIFICATIONS adds significant overhead and will be disab
pycharm环境包导入到另外一个环境
PDF不能打印和复制的问题如何解决?
jvm线程状态
C语言的内置宏(定义日志宏)
Altium designer软件常用最全封装库,包含原理图库、PCB库和3D模型库
static静态关键字和继承
ByteDance Interview Questions: Mirror Binary Tree 2020
Use of PlantUML plugin in idea
随机推荐
Remember a nest.js route that matches all the path problems that follow
字节跳动面试题之镜像二叉树2020
ZIP压缩包文件删除密码的方法
Use baidu EasyDL intelligent bin
C语言实现顺序栈和链队列
mysql 总结
The AD in the library of library file suffix. Intlib. Schlib. Pcblib difference
Import the pycharm environment package into another environment
A test engineer with an annual salary of 35W was laid off. Personal experience: advice that you have to listen to
[GO], arrays and slices
直接用的zip包 缺少很多依赖,pip没有,感觉用anaconda create一个环境会方便点
单例 DCL(double check lock) 饱汉模式和饿汉模式
字节跳动笔试题2020 (抖音电商)
String.toLowerCase(Locale.ROOT)
APP product source data interface (taobao, jingdong/spelling/suning/trill platform details a lot data analysis interface) code and docking tutorial
Fragments
PDF不能打印和复制的问题如何解决?
DevNet: Deviation Aware Networkfor Lane Detection
Quectel EC20 4G module dial related
Thread Pool Summary