首页 > 其他分享 >Minimum Steiner Tree 题解

Minimum Steiner Tree 题解

时间:2024-08-25 16:16:45浏览次数:13  
标签:遍历 删除 题解 Tree Steiner Minimum

原题,详见P10723

几乎相同,我们只需要以一个需要选择的点为根,遍历子树看看有没有出现需要选择的点,然后直接去删除即可,可以看我的博客

但是我们也可以换一种做法,用类似拓扑排序的算法。

先找到所有只连一条边且没有被选择的点,然后放进队列,接着依次取出队头遍历与它相连的点,同时记录一下是否访问,如果不是需要选择的点而且没有访问而且只连一条边,则可以删除。最后用总结点数减去可以删除的节点数即可。

赛时记录

标签:遍历,删除,题解,Tree,Steiner,Minimum
From: https://www.cnblogs.com/Lydic/p/18379058

相关文章

  • k8s中coredns访问连接拒绝问题解决
    问题现象1、节点访问coredns连接拒绝2、内部pod无法正常进行解析问题解决思路检查CoreDNSPod状态是否正常[root@k8s-master01~]#kubectlgetpods-nkube-system-lk8s-app=kube-dnsNAMEREADYSTATUSRESTARTSAGEcoredns-7b8d6fc5......
  • CSP-J 2023 初赛试题解析(第三部分:完善程序(1-2))
    第一题补全后完整代码:#include<iostream>#include<vector>usingnamespacestd;intfind_missing(vector<int>&nums){intleft=0,right=nums.size()-1;while(left<right){intmid=left+(right-left)/2;if(nums[mi......
  • 洛谷SCP 2024 第一轮(初赛 J 组)模拟题解析(第三部分:完善程序(1-2))
    完善程序一(补全)#include<bits/stdc++.h>usingnamespacestd;constintMAXN=100000;intn;intvis[MAXN],a[MAXN];vector<int>ans;intcheck(intk){intx=n,top=0;for(inti=0;i<=k;i++)vis[i]=0;while(x......
  • 题解:P10358 [PA2024] Obrazy
    题解:P10358[PA2024]Obrazy题目传送门即当最小的画框都不可能覆盖整个矩形墙面时,输出−1。[PA2024]Obrazy题目背景PA20243C题目描述题目译自PA2024Runda3Obrazy,感谢Macaronlin提供翻译给定尺寸为$h\timesw$的矩形墙面,以及$n$种尺寸的正方形画框,每种尺寸......
  • SP10502 VIDEO - Video game combos 题解
    题目传送门前置知识AC自动机解法多模式串匹配考虑AC自动机。令\(f_{i,j}\)表示前\(i\)个字符,当前运行到AC自动机的状态\(j\)时的最大得分。状态转移方程为\(f_{i,k}=\max\limits_{k\inSon(j)}\{f_{i-1,j}+sum_{k}\}\),其中\(sum_{k}\)表示fail树上以\(k......
  • 历年CSP-J初赛真题解析 | 2015年CSP-J初赛阅读程序(23-26)
    学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。附上汇总贴:历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客#include<iostream>usingnamespacestd;intmain(){inta,b,c;a=1;b=2;c=3;if(a>b){......
  • abc368 题解
    切了ABCDF,G赛后1min切了(恼比赛链接:https://atcoder.jp/contests/abc368A-Cut题意:给定一个长度为\(n\)的序列,先输出后\(k\)个数,在输出前\(n-k\)个数。思路:按题意模拟即可。代码:https://atcoder.jp/contests/abc368/submissions/57030066B-Decrease2maxel......
  • ABC 368D Minimum Steiner Tree
    题意给你一颗由N个点组成的树,指定K个节点,求包含这K个节点的最小子树的大小思路考虑正难则反,我们从开始的树当中剪掉那些没有任何指定点的子树,剩下来的子树就是最小的、能包含所有指定节点的子树。关于剪去这个操作,就是dfs一旦遇到以当前节点为根的子树没有任何指定点时,就停止df......
  • CF241B Friends 题解
    是异或粽子的超级加强版,但是本题因为\(m\)很大,不能套用那一题的解法。换一种思路:考虑把\(a_i\)从高位到低位插入0-1Trie之后,二分第\(m\)大,通过第\(m\)大求答案。对于二分的一个值\(x\),枚举每个位置\(i\),在0-1Trie上找与\(a_i\)异或值大于等于\(x\)的值的......
  • qoj8546题解补充
    题解中第二种解法并没有具体解释是如何归纳的(害笔者想了两天两夜),这里给一个证明。考虑答案为(n,n)时,只需要全取max即可,接下来我们从n往n-1归纳,接下来所有位置初始都是取max的情况1:a中的n和b中的n在同一个位置上,我们只需在这个位置上取min即可归纳到n-1,那么接下来我们钦定不会......