[TIOJ] 1292. H.佔邊砍樹
題目連結:http://tioj.infor.org/problems/1292
裸樹上最小點覆蓋。而樹上最小點覆蓋該如何做呢?,不妨考慮先DFS一遍取得整棵樹的構造,之後從葉子走上去(可直接用DFS序列倒著跑),若自己及自己的爸爸都沒有被任何點覆蓋,則把自己的爸爸放到點覆蓋集,因為這樣可以保證把所有點都放進去,而且因為是放爸爸進去,所以可以拿到最小的點覆蓋集。
裸樹上最小點覆蓋。而樹上最小點覆蓋該如何做呢?,不妨考慮先DFS一遍取得整棵樹的構造,之後從葉子走上去(可直接用DFS序列倒著跑),若自己及自己的爸爸都沒有被任何點覆蓋,則把自己的爸爸放到點覆蓋集,因為這樣可以保證把所有點都放進去,而且因為是放爸爸進去,所以可以拿到最小的點覆蓋集。
#include <bits/stdc++.h>
using namespace std;
#define N 10000
vector<int> tree[N+10];
int deep[N+10];
vector<int> arr;
bitset<N+10> poped;
void DFS(int,int,int);
int n;
int main(){
scanf("%d",&n);
for(int i=0;i<n-1;i++){
int s,e;
scanf("%d%d",&s,&e);
tree[s].push_back(e);
tree[e].push_back(s);
}
int cnt=0;
DFS(1,-1,0);
for(int i=arr.size()-1;i>0;i--){
int cc=arr[i];
int ff=arr[i-1];
if(deep[ff]>=deep[cc])continue;
if(!poped[ff]&&!poped[cc]){
poped[ff]=1;
poped[cc]=1;
cnt++;
}
}
printf("%d",cnt);
return 0;
}
void DFS(int w,int f,int d){
deep[w]=d;
for(auto i : tree[w]){
if(i==f)continue;
arr.push_back(w);
DFS(i,w,d+1);
}
if(tree[w].size()==1&&f!=-1) arr.push_back(w);
}
留言
張貼留言