是否有 O(n) 中的演算法來計算加權樹的最大匹配？
我只找到了未加權樹或二部圖的演算法。我在將這些演算法轉換為樹時遇到了一些麻煩。用筆和紙我還發現，未加權樹的演算法不適用于加權樹。我認為遞回它需要的不僅僅是 O(n)，還有哪些選擇？動態規劃可以嗎？
幫助將不勝感激。謝謝 ：）
uj5u.com熱心網友回復：
O(n) 動態規劃解決方案是選擇任意一個節點作為根，然后在根匹配和根不匹配的情況下遞回計算每個節點的子樹中的最大匹配。
在后序 (DFS) 中計算很容易：節點的最大根不匹配匹配只是每個子子樹的最佳匹配的總和。一個節點的最大根匹配匹配是與它的一個孩子的根不匹配子樹匹配的根的最佳匹配，添加到其他孩子的最佳匹配中。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/350534.html
下一篇：無限迷宮生成演算法
最近新學習了下區塊鏈這方面的知識，所學不多，給大家分享下。 # 1. 關于web3j web3j是一個高度模塊化，反應性，型別安全的Java和Android庫，用于與智能合約配合并與以太坊網路上的客戶端（節點）集成。 # 2. 準備作業 jdk版本1.8 引入maven <dependency> < ......
uj5u.com 2020-09-10 03:03:06 more前言 部署智能合約有多種方式，命令列的瀏覽器的渠道都有，但往往跟我們程式員的風格不太相符，因為我們習慣了在IDE里寫了代碼然后打包運行看效果。 雖然現在IDE中已經存在了Solidity插件，可以撰寫智能合約，但是部署智能合約卻要另走他路，沒辦法進行一個快捷的部署與測驗。 如果團隊管理的區塊節點多、 ......
uj5u.com 2020-09-10 03:03:12 more前言 谷歌身份驗證器，前些年大家都比較陌生，但隨著國內互聯網安全的加強，它越來越多地出現在大家的視野中。 比較廣泛接觸的人群是國際3A游戲愛好者，游戲盜號現象嚴重+國外賬號安全應用廣泛，這類游戲一般都會要求用戶系結名為“兩步驗證”、“雙重驗證”等，平臺一般都推薦用谷歌身份驗證器。 后來區塊鏈業務風靡 ......
uj5u.com 2020-09-10 03:03:17 more目錄 ##1.1 ASCII編碼 ASCII（American Standard Code for Information Interchange，美國資訊交換標準代碼）是基于拉丁字母的一套電腦編碼系統，主要用于顯示現代英語和其他西歐語言。它是現今最通用的單位元組編碼系統，并等同于國際標準ISO/IE ......
uj5u.com 2020-09-10 03:04:50 moreNTP時鐘服務器的特點（京準電子） NTP時鐘服務器的特點（京準電子） 京準電子官V——ahjzsz 首先對時間同步進行了背景介紹，然后討論了不同的時間同步網路技術，最后指出了建立全球或區域時間同步網存在的問題。 一、概 述 在通信領域，“同步”概念是指頻率的同步，即網路各個節點的時鐘頻率和相位同步 ......
uj5u.com 2020-09-10 03:05:47 more標準化考場時鐘同步系統推進智能化校園建設 標準化考場時鐘同步系統推進智能化校園建設 安徽京準電子科技官微——ahjzsz 一、背景概述隨著教育事業的快速發展，學校建設如雨后春筍，隨之而來的學校教育、管理、安全方面的問題成了學校管理人員面臨的最大的挑戰，這些問題同時也是學生家長所擔心的。為了讓學生有更 ......
uj5u.com 2020-09-10 03:05:51 more北斗對時服務器（北斗對時設備）電力系統應用 北斗對時服務器（北斗對時設備）電力系統應用 京準電子科技官微（ahjzsz） 中國北斗衛星導航系統（英文名稱：BeiDou Navigation Satellite System，簡稱BDS），因為是目前世界范圍內唯一可以大面積提供免費定位服務的系統，所以 ......
uj5u.com 2020-09-10 03:06:20 moreMetamask錢包是一種基于區塊鏈技術的數字貨幣錢包，它允許用戶在安全、便捷的環境下管理自己的加密資產。Metamask錢包是以太坊生態系統中最流行的錢包之一，它具有易于使用、安全性高和功能強大等優點。 本文將詳細介紹Metamask錢包的功能和使用方法。 一、 Metamask錢包的功能 數字資 ......
uj5u.com 2023-04-20 08:46:47 more在上個實驗中，我們已經實作了簡單智能合約實作及客戶端開發，但該實驗中智能合約只有基礎的增刪改查功能，且其中的資料管理功能與傳統 MySQL 比相差甚遠。本文將在前面實驗的基礎上，將 Hyperledger Fabric 的默認資料庫支持 LevelDB 改為 CouchDB 模式，以實作更復雜的資料... ......
uj5u.com 2023-04-16 07:28:31 moreGet Started NuGet You can run the following command to install the Tron.Wallet.Net in your project. PM> Install-Package Tron.Wallet.Net 配置 public reco ......
uj5u.com 2023-04-14 08:08:00 more概述： 2023 年 2 月 8 日，針對 DKP 協議的閃電貸攻擊導致該協議的用戶損失了 8 萬美元，因為 execute() 函式取決于 USDT-DKP 對中兩種代幣的余額比率。 智能合約黑客概述： 攻擊者的交易：0x0c850f，0x2d31 攻擊者地址：0xF38 利用合同：0xf34ad ......
uj5u.com 2023-04-07 07:46:09 more// SPDX-License-Identifier: GPL-3.0 pragma solidity >=0.7.0 <0.9.0; import "hardhat/console.sol"; //ERC20 同質化代幣，每個代幣的本質或性質都是相同 //ETH 是原生代幣，它不是ERC20代幣, ......
uj5u.com 2023-03-21 07:56:29 more在solidity語言中 參考型別修飾符(參考型別為存盤空間不固定的數值型別) memory、calldata與storage,它們只能修飾參考型別變數，比如字串、陣列、位元組等... memory 適用于方法傳參、返參或在方法體內使用，使用完就會清除掉，釋放記憶體 calldata 僅適用于方法傳參 ......
uj5u.com 2023-03-08 07:57:54 more在solidity語言中 注釋符為// 注解符為/* 內容*/ 或者 是 ///內容 注解中含有這幾個標簽給予我們使用 @title 一個應該描述合約/介面的標題 contract, library, interface @author 作者的名字 contract, library, interf ......
uj5u.com 2023-03-08 07:57:49 more【代碼注釋自動生成方法綜述】 這些評測指標主要來自機器翻譯和文本總結等研究領域,可以評估候選文本(即基于代碼注釋自動方法而生成)和參考文本(即基于手工方式而生成)的相似度. BLEU指標^[^?88^^?^]^:其全稱是bilingual evaluation understudy.該指標是最早用于 ......
uj5u.com 2023-02-23 07:27:39 more最近，一個幽靈，Web3的幽靈，在網路游蕩，它叫Damus，這玩意詮釋了什么叫做病毒式營銷，滑稽的是，一個Web3產品卻在Web2的產品鏈上瘋狂傳銷，各方大佬紛紛為其背書，到底發生了什么？Damus的葫蘆里，賣的是什么藥？ 注冊和簡單實用 很少有什么產品在用戶注冊環節會有什么噱頭，但Damus確實出 ......
uj5u.com 2023-02-05 06:48:39 more