持续填坑中…
A
B
C
原题链接
题意:给你一个n个节点的无根树,现在要你找到最少的k条链使得这k条链能覆盖整个树边
题解:
#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; struct edge{ int v,next; }e[maxn]; struct node{ int id; int dfn; bool operator <(const node &rhs) const{ return dfn<rhs.dfn; } }p[maxn]; int n; int dfn[maxn]; int head[maxn],cnt=0; int deg[maxn]; bool vis[maxn]; void add(int u,int v){ e[++cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } int ct=0; void dfs(int x){ dfn[x]=++ct; for (int i=head[x];i;i=e[i].next){ int v=e[i].v; if(!vis[v]){ vis[v]=1; dfs(v); } } } int main(){ scanf("%d",&n); for (int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); add(u,v);add(v,u); deg[u]++; deg[v]++; } if(n == 1){ printf("0n");return 0; } if(n == 2){ printf("1n");return 0; } for (int i=1;i<=n;i++){ if(deg[i] != 1){//找到第一个非叶节点,把其作为树根,求一个dfs序 vis[i] = 1; dfs(i); break; } } int tot = 0; for (int i=1;i<=n;i++){ if(deg[i] == 1){//选出叶子结点 p[++tot].id = i; p[tot].dfn = dfn[i]; } } sort(p+1,p+1+tot); printf("%dn",(tot+1)/2); for (int i=1;i<=(tot+1)/2;i++){ int a=p[i].id,b=p[tot/2+i].id; printf("%d %dn",a,b); } return 0; }
D
E
F
G
H
c/c++开发分享2020牛客暑期多校第二场题解地址:https://blog.csdn.net/qq_43597227/article/details/107325018
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/599018.html