题目来源:https://ac.nowcoder.com/acm/contest/5667/C
题意:给一棵没有根的树,连接其中两个节点组成一条链,使树中的每一条边至少被一条链覆盖。 输出最少的链数量+其中任一个解决方案。
做题历程:比赛中我看了这道题老半天,没有想到一个好的结构将这样的树储存起来,而且一开始题意不是太明白,后来才发现到底是个什么意思...也没有想到一个好的解决办法将路径输出。
赛后看出题解后反思思路:
如上图所示,这个最少链数量其实和叶子节点的个数有关(如图中所示),分两种情况,当叶子节点数目为偶数,直接除以二,当叶子节点数目为奇数,除以二加一。可以用dfs来遍历,找出叶子节点的数目。但是有一个注意点就是,方案里的路径可能会涉及相邻的叶子节点(如图样例1),所以要想法规避这一点。具体见代码:
#include<bits/stdc++.h> using namespace std; int n,flag,t=0; int a[200001]; vector<int> v[200001];//用向量的形式存储这个树 void dfs(int x,int y)//dfs来统计叶子节点数,x为当前节点,y为其x的双亲节点 { for(int i=0;i<v[x].size();i++) if(v[x][i]!=y) dfs(v[x][i],x); if(v[x].size()==1) { t++; a[t]=x; } } int main() { int i,x,y; int t1; cin>>n; for(i=1;i<n;i++) //存储这个树 { cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } if(n==1) cout<<"0"<<endl; else if(n==2) cout<<"1"<<endl<<"1 2"<<endl; else { for(i=1;i<=n;i++) //找到一个非叶子节点 if(v[i].size()>1) { dfs(i,i); flag=i; break; } if(t%2==0) //这个t1来存最后结果 t1=t/2; else t1=t/2+1; cout<<t1<<endl; for(i=1;i<=t/2;i++) cout<<a[i]<<" "<<a[t1+i]<<endl; if(t%2==1) cout<<flag<<" "<<a[t1]<<endl; } return 0; }