@Junlier
2018-08-31T22:12:49.000000Z
字数 1356
阅读 1963
贪心
- 显然这是一棵树(这个就不多bb了,树的性质)
- 很容易发现一个性质,如果一条链走完,我们必须回头再走一次那条链(或一部分)才可以走到更多的点
- 所以为了减少这个损失,我们以最长链(从起点开始的最长链)的终点(最低端)为终点(步数走完不须回头),既然做到减少了最多的不必要,那么这样一定会是最优的。(可以证明是最优的,只是我不知道,
举不出反例我就写了)- 考虑除了走最长链步数之外的剩余步数。最好画个图,既然我们一定要走最长链,那么可以看做一根树干上长了其他的一些枝条,我们的剩余步数就是用来走这些地方的,很容易证明一定可以额外走到 (剩余步数/2) 个节点(最长链之外)。
- 没了……(代码实现基本没难度)
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#define rg register
#define il inline
#define lst long long
#define ldb long double
#define N 150
using namespace std;
const int Inf=1e9;
int n,step,cnt;
int ans,ans_st;
struct EDGE{
int to,nxt;
}ljl[N<<1];
int hd[N];
int vis[N];
il int read()
{
rg int s=0,m=0;rg char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
il void add(rg int p,rg int q)
{
ljl[++cnt]=(EDGE){q,hd[p]},hd[p]=cnt;
}
void dfs(rg int fm,rg int now,rg int st,rg int ss)
{
if(st>step)return;
if(ss>ans)ans=ss,ans_st=st;
vis[now]=1;
for(rg int i=hd[now];i;i=ljl[i].nxt)
{
rg int qw=ljl[i].to;
if(qw==fm)continue;
if(!vis[qw])dfs(now,qw,st+1,ss+1);
}
}
int main()
{
n=read(),step=read();
for(rg int i=1;i<n;++i)
{
rg int p=read(),q=read();
add(p,q),add(q,p);
}
dfs(0,0,0,1);
if(ans_st==step)printf("%d\n",ans);
else printf("%d\n",min(ans+(step-ans_st)/2,n));
return 0;
}
代码还是很好看的,只是变量为了通俗就很丑