洛谷 U140120 漂亮国大选
洛谷 漂亮
2023-09-11 14:20:14 时间
洛谷 U140120 漂亮国大选
题目背景
漂亮国是一个团结、民主的国家。
题目描述
这个国家有NN个城市,N-1N−1条双向道路连接着这些城市。因为漂亮国是一个团结的国家,所以从任何一个城市你都可以通过道路到达任何其他城市。是的,你是对的——漂亮国的拓扑结构是一棵没有方向的树。
漂亮国有很多党派,每个党派会“把控”一些道路。当然,每条道路只能被一个党派把控。
现在漂亮国要进行总统大选。在大选前,上一任总统有权重新安排所有道路的把控党派。上任总统安排道路的原则是:让整个国家看起来更民主。漂亮国国民对于民主的定义是:如果有一个党派拥有两条或以上的进入某个城市的道路,那么这个城市就不是一个民主的城市。
假设你是漂亮国国家道路安排局局长。总统希望,这样不民主的城市的数量不超过KK个。请你回答总统:最少需要多少个不同的党派把控道路?
输入格式
从文件election.inelectio**n.i**n中读入数据。
第一行两个整数N,KN,K,意义如题目描述所示。
接下来的N-1N−1行,每行两个整数u,vu,v,表示存在着一条从uu城市到vv城市的道路。
输出格式
输出到文件election.outelectio**n.out中。
一行一个整数ansans,表示最少所需党派数量。
命题背景:
预言梦:BIDEN WINS!
。。。找了好久的紫题,觉得挺好没细看就编成了题。结果其实是水题?
哭哭哭哭哭哭哭。
原题是打每条边的颜色,但是那需要SPJ,所以不想写了。就改了个题。越改越水。
不想改了,送大家分分吧。
也是练大家心态。
相信自己。
YY出的算法就是对的,不要因为它是T3就觉得它假了...其实真就是对的。
题解:
所以没啥可讲的,就是一贪心。
随便维护第二问就好。咋的都T不了。
代码:
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=2e5+5;
int n,k,r;
int tot,head[maxn],to[maxn<<1],nxt[maxn<<1];
int cnt,ans[maxn];
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
struct node
{
int id,d;
}du[maxn];
bool cmp(node a,node b)
{
return a.d<b.d;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
du[i].id=i;
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
du[x].d++,du[y].d++;
}
sort(du+1,du+n+1,cmp);
r=du[n-k].d;
printf("%d\n",r);
for(int i=n-k;i<=n;i++)
if(du[i].d>r)
ans[++cnt]=du[i].id;
sort(ans+1,ans+cnt+1);
for(int i=1;i<=cnt;i++)
printf("%d ",ans[i]);
puts("");
return 0;
}
相关文章
- Java实现洛谷 P1062 数列
- Java实现 洛谷 P1208 [USACO1.3]混合牛奶 Mixing Milk
- Java实现 洛谷 P1170 兔八哥与猎人
- Java实现 洛谷 P1423 小玉在游泳
- Java实现 洛谷 P1567 统计天数
- Java实现 洛谷 P1028 数的计算
- Java实现 洛谷 P2118 比例简化
- Java实现 洛谷 P1487 陶陶摘苹果(升级版)
- Java实现 洛谷 P1426 小鱼会有危险吗
- java实现 洛谷 P1427 小鱼的数字游戏
- Java实现 洛谷 P1015 回文数(N进制回文数)
- (Java实现) 洛谷 P1319 压缩技术
- (Java实现) 洛谷 P1012 拼数
- 【洛谷】P1010 幂次方
- 洛谷——P5019 NOIP 铺设道路(java实现)