欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

2020牛客暑期多校第二场题解

程序员文章站 2022-06-23 09:41:37
持续填坑中…ABC原题链接题意:给你一个n个节点的无根树,现在要你找到最少的k条链使得这k条链能覆盖整个树边题解:#include 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 &...

持续填坑中…

A

B

C

原题链接
题意:给你一个n个节点的无根树,现在要你找到最少的k条链使得这k条链能覆盖整个树边

题解:
2020牛客暑期多校第二场题解

#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("0\n");return 0;
    }
    if(n == 2){
        printf("1\n");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("%d\n",(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 %d\n",a,b);
    }
    return 0;
}

D

E

F

G

H

本文地址:https://blog.csdn.net/qq_43597227/article/details/107325018