| 题目名称 | 489. 树的最大匹配 |
|---|---|
| 输入输出 | treeb.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2010-11-01加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：24， 提交：67， 通过率：35.82% | ||||
 雾茗 |
100 | 0.000 s | 0.00 MiB | C++ |
 youming1 |
100 | 0.002 s | 0.36 MiB | C++ |
 kaaala |
100 | 0.003 s | 0.30 MiB | C++ |
 Czb。 |
100 | 0.003 s | 0.32 MiB | C++ |
 苏轼 |
100 | 0.003 s | 0.36 MiB | C++ |
|
youming1 |
100 | 0.003 s | 0.36 MiB | C++ |
 CloudTower |
100 | 0.003 s | 0.38 MiB | C++ |
 天下第一的吃货殿下 |
100 | 0.003 s | 2.10 MiB | Pascal |
 .Xmz |
100 | 0.003 s | 3.26 MiB | C++ |
 不列颠呆毛 |
100 | 0.004 s | 3.18 MiB | C++ |
| 本题关联比赛 | |||
| 20101101 | |||
| 20101101 | |||
| 关于 树的最大匹配 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
推销一波题解哈https://www.cnblogs.com/XLINYIN/p/11476992.html
| ||||
|
一个树规即可，不必开高精，每个节点两种记录状态
| ||||
|
两个树规
| ||||
瑆の時間~無盡輪迴·林蔭
Truth.Cirno【题目描述】
给一棵树，你可以匹配有边相连的两个点，问这棵树的最大匹配是多少，并且计算出有多少种最大匹配
【输入格式】
第一行一个数 N ，表示有多少个结点。
接下来 N 行，每行第一个数，表示要描述的那个结点的编号。然后一个数 m ，表示这个结点有 m 个儿子，接下来 m 个数，表示它的 m 个儿子的编号。
【输出格式】
输出两行，第一行为最大匹配数，第二行输出最大匹配方案数。
【输入样例】
7
1 3 2 4 7
2 1 3
4 1 6
3 0
7 1 5
5 0
6 0
【输出样例】
3
4
【数据规模】
N<=1000, 其中 40% 的数据答案不超过 10^7