「BZOJ1907」树的路径覆盖
Description
Input
Output
Sample Input
1
7
1 2
2 3
2 4
4 6
5 6
6 7
7
1 2
2 3
2 4
4 6
5 6
6 7
Sample Output
3
HINT
题解
从下往上直接贪心T T
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n,cnt; int last[10005],v[10005]; bool mark[10005]; struct edge{int to,next;}e[20005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void dfs(int x,int f) { v[x]=1; int tot=0; for(int i=last[x];i;i=e[i].next) { if(e[i].to==f)continue; dfs(e[i].to,x); v[x]+=v[e[i].to]; if(!mark[e[i].to])tot++; } if(tot>=2)v[x]-=2,mark[x]=1; else if(tot==1)v[x]--; } int main() { T=read(); while(T--) { cnt=0; memset(last,0,sizeof(last)); memset(v,0,sizeof(v)); memset(mark,0,sizeof(mark)); n=read(); for(int i=1;i<n;i++) { int a=read(),b=read(); insert(a,b); } dfs(1,0); printf("%d\n",v[1]); } return 0; } |
计数器 9300544
OI 课件=>
OI 课件=>
请教一下这题的原题是spoj的PT07F – A short vacation in Disneyland 但是那题要求输出方案，那应该怎么写会比较简单？