首页 > 其他 > 详细

BZOJ-1907 树的路径覆盖 贪心

时间:2019-10-17 10:07:06      阅读:64      评论:0      收藏:0      [点我收藏+]

题意:给一个n个点的树,求树的最小路径覆盖。(这个最小路径覆盖不能有重点)

解法:往图论方向想很久,想得太复杂了,其实直接贪心。这个大佬题解写得很好:

https://blog.csdn.net/blue_cuso4/article/details/78079730

 

 1 #include <bits/stdc++.h>
 2 #define N 10005
 3 using namespace std;
 4 int tot,nxt[N*2],point[N],v[N*2],size[N];bool vis[N];
 5 void cl(){tot=0; memset(point,0,sizeof(point));memset(size,0,sizeof(size));memset(vis,0,sizeof(vis));}
 6 
 7 void addline(int x,int y) {
 8     ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
 9 }
10 
11 void dfs(int x,int fa) {
12     int cnt=0;
13     size[x]=1;
14     for (int i=point[x];i;i=nxt[i])
15       if (v[i]!=fa)
16       {
17         dfs(v[i],x);
18         size[x]+=size[v[i]];
19         if (!vis[v[i]]) cnt++;
20       }
21     if (cnt>=2) size[x]-=2,vis[x]=true;//可以被当做一个拐点,折起来节点数-2 
22     else if (cnt==1) size[x]--;//只能和这个点一起走到顶 
23 }
24 
25 int main()
26 {
27     int T,i,n;
28     scanf("%d",&T);
29     while (T--) {
30         cl();
31         scanf("%d",&n);
32         for (i=1;i<n;i++) {
33             int x,y;
34             scanf("%d%d",&x,&y);
35             addline(x,y),addline(y,x);
36         }
37         dfs(1,0);
38         printf("%d\n",size[1]);
39     }
40 }

 

BZOJ-1907 树的路径覆盖 贪心

原文:https://www.cnblogs.com/clno1/p/11688717.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!