Codeforces 369 C Valera and Elections
2024-08-27 18:33:12
题意:现在有n个候选人, 有n-1条路, 如果选择了这个候选人, 这个候选人就会将从自己这个城市到1号城市上所有坏的路都修复一下,现在求最小的候选人数目, 如果答案有多种情况输出任何一种都可以。
输入:x y k 表示x与y之间有一条双向通道, k==1 表示这路是好的, k == 2表示这条路是坏的。
题解: 从1开始dfs搜索, 往外走, 如果遇到坏的城市就标记一下, 然后继续往外走, 如果更远的地方有一个坏的路就用更远地方的城市候选人代替这个标记的这个人。
代码:
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int, int> pll;
const int INF = 0x3f3f3f3f;
const int N = 1e5+;
vector<pll> E[N];
bool vis[N];
int cnt = ;
void dfs(int x, int n, int last)
{
for(int i = ; i < E[x].size(); i++)
{
pll tmp = E[x][i];
if(tmp.fi == last) continue;
if(tmp.se == )
{
cnt++;
if(vis[n]) cnt--, vis[n] = ;
vis[tmp.fi] = ;
dfs(tmp.fi, tmp.fi, x);
}
else dfs(tmp.fi, n, x);
}
}
int main()
{
int n;
scanf("%d",&n);
int x, y, ok;
for(int i = ; i < n; i++)
{
scanf("%d%d%d",&x,&y,&ok);
E[x].push_back(pll(y,ok));
E[y].push_back(pll(x,ok));
}
memset(vis, , sizeof(vis));
dfs(,,);
printf("%d\n", cnt);
for(int i = ; i <= n; i++)
if(vis[i]) printf("%d ",i);
return ;
}
最新文章
- 4. ValueStack 和 OGNL
- 判断表字段是否存在default约束
- 转:NodeJS、NPM安装配置步骤
- ByteBuffer解析
- Unity3D ShaderLab 使用渐变纹理着色
- ace-min.css
- Android 使用 popupWindow实现弹层并操作弹层元素
- Ubuntu下安装Redis并实现远程访问
- mac iterm2安装、sshpass密码记住
- C#中的Finalize,Dispose,SuppressFinalize(转载)
- JAVA String类型和原型模式
- 你可能不知道的printf
- [转帖] 百度知道: KMS 和OSPP
- php检测服务器是否可用 不可用发动钉钉消息
- python基础学习23----IO模型(简)
- CAS操作原理分析
- Linux下串口編程遇到的接收数据错误及原因(0x0d,0x11接收错误)
- java 实现输出姓和名
- LeetCode: Gray Code 解题报告
- unity3d绘画手册-------地形高度调节