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

2020牛客暑期多校训练营(第二场)Cover the Tree

程序员文章站 2024-03-17 08:56:46
...

题目描述

Given an unrooted tree, you should choose the minimum number of chains that all edges in the tree are covered by at least one chain. Print the minimum number and one solution. If there are multiple solutions, print any of them.

输入描述:

2020牛客暑期多校训练营(第二场)Cover the Tree

输出描述:2020牛客暑期多校训练营(第二场)Cover the Tree

连线的话最好是两个叶子节点一连,最后一个点随便连。
于是就要把叶子节点按dfs序标号,然后两个一输出

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[200010],b[200020],n,m,i,j,k,l,o,p;
vector<ll> v[200100];
void dfs(ll pos,ll fa)//dfs标号
{
    if (a[pos]==1)
    {
        b[++m]=pos;
        return;
     }
    for (ll i=0;i<v[pos].size();i++)
     {
        if (v[pos][i]==fa) continue;
        dfs(v[pos][i],pos);
     }
}
int main()
{
    scanf("%lld",&n);
    if (n==2)//特判,如果就两个节点直接输出1
    {
        printf("1\n");
        return 0;
    }
    for (i=1;i<n;i++)
     {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        a[x]++;a[y]++;
        v[x].push_back(y);
        v[y].push_back(x);
     }
    m=0;
    ll root=0;
    for (i=1;i<=n;i++)
     if (a[i]>1)
      {
        dfs(i,-1);
        root=i;
        break;
      }
    printf("%lld\n",(m+1)/2);
    for (i=1;i<=m/2;i++)
     printf("%lld %lld\n",b[i],b[m/2+i]);
    if (m%2) printf("%lld %lld\n",b[m/2+1],root);
}

然后只有80分。。。
查了之后
发现会被这个图卡住
2020牛客暑期多校训练营(第二场)Cover the Tree
继菊花图后的另一个奇怪的图
然后改一下输出顺序,AC

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[200010],b[200020],n,m,i,j,k,l,o,p;
vector<ll> v[200100];
void dfs(ll pos,ll fa)
{
	if (a[pos]==1)
	{
		b[++m]=pos;
		return;
	 }
	for (ll i=0;i<v[pos].size();i++)
	 {
	 	if (v[pos][i]==fa) continue;
	  	dfs(v[pos][i],pos);
	 }
}
int main()
{
	scanf("%lld",&n);
	if (n==2)
	{
		printf("1\n");
		return 0;
	}
	for (i=1;i<n;i++)
	 {
	 	ll x,y;
	 	scanf("%lld%lld",&x,&y);
	 	a[x]++;a[y]++;
	 	v[x].push_back(y);
	 	v[y].push_back(x);
	 }
	m=0;
	ll root=0;
	for (i=1;i<=n;i++)
	 if (a[i]>1)
	  {
	  	dfs(i,-1);
	  	root=i;
	  	break;
	  }
	printf("%lld\n",(m+1)/2);
	for (i=1;i<=m/2;i++)
	 printf("%lld %lld\n",b[i],b[(m+1)/2+i]);
	if (m%2) printf("%lld %lld\n",b[m/2+1],root);
}
相关标签: dfs 算法