题目链接
题目大意
给一棵树,要求选择最少的点对,所有点对连成的链要覆盖所有的边。边可以重复覆盖,求最少的点对,以及写出点对
题目思路
首先你从以一个度不为1的点作为根节点。然后你每次都连接一个叶子节点,这样显然是所有的边都可以被覆盖。即答案为度为1的点的个数,但是这样显然很大,可以优化,可以相当于把根节点当作中间节点,让叶子节点两两相连,显然答案已经出来了,就是但是怎么两两配对是一个问题,我比赛的时候差不多已经想到了dfs序,但是还是没写出来,下面就直接看标程吧。
代码
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define debug printf("I am here\n");
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
int n,deg[maxn],head[maxn],ans[maxn],root,tot,cnt;
struct node{
int to,next;
}e[maxn<<1];
vector<int > vec;
void add(int u,int v){
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
deg[u]++;
}
void dfs(int son,int fa){
if(deg[son]==1){
ans[++tot]=son;
}
for(int i=head[son];i;i=e[i].next){
if(e[i].to==fa) continue;
dfs(e[i].to,son);
}
}
signed main(){
scanf("%d",&n);
for(int i=1,u,v;i<=n-1;i++){
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
for(int i=1;i<=n;i++){
if(deg[i]!=1){
root=i;
break;
}
}
dfs(root,root);
int half=(tot+1)/2;
printf("%d\n",half);
if(tot%2==1){
ans[++tot]=root;
}
for(int i=1;i<=half;i++){
printf("%d %d\n",ans[i],ans[i+half]);
}
return 0;
}
本文地址:https://blog.csdn.net/m0_46209312/article/details/107325599
您可能感兴趣的文章:
- RabbitMQ单机集群搭建出现Error: unable to perform an operation on node 'rabbit1@ClusterNode1'
- DotNetty在window和linux下的性能对比
- .net core 图片合并,图片水印,等比例缩小,SixLabors.ImageSharp
- WPF简单的分页控件实现
- ASP.NET中实现中文简/繁体自动转换的类
- 前后端分离,https站点无法通过Ajax访问http资源(Mixed Content,The page at 'https://xxx.com' was loaded over HTTPS)
- layui,返回的数据不符合规范,正确的成功状态码 (code) 应为:0
如您对本文有疑问或者有任何想说的,请点击进行留言回复,万千网友为您解惑!
网友评论