两幅树形图，其实就是除了源点之外，所有点都有两条入边，有任意多的出边，基于这个性质，构造网络流模型。

于是拆点，x拆成x与x'

添加源汇s, t
s连到所有x，容量无穷大
所有x'连到汇，容量为2

如果有边a->b
则连边a->b'，容量为1

求最大流，如果总流量为2n-2，则有解
每个点都有两条流流入，也就是树形图中的两个入边

输出解很容易，对于每个点，任选一条入边，这样就构造了第一幅树形图；剩下的肯定是另外一幅树形图

题目还蛮有新意，让人想做，就是描述太麻烦了

按这个思路这个题应该不难才对，但不明白为什么1人ac，没时间做acm了，有人这样ac了pm一下

• 树形图应该是以L(节点1)为根的... (347) gf_lu 2009-08-28 15:50:51
  • 我没有说不是啊，你没看明白？ (0) majia_ 2009-08-28 16:12:58
    • 没有看到你构图的时候对1有特殊对待 (0) gf_lu 2009-08-28 17:11:35
    • 另外x - x' 的容量为多少？ (0) gf_lu 2009-08-28 17:15:10
• 请问一下，能保证树的有向性吗？ (347) tomorrow911 2009-08-29 14:52:42
• Re:对不起啊，一开始说错了，正确的解法是这样的： (842) majia_ 2009-10-02 21:43:00
• Re:想做但又没时间，提供个思路，谁ac了通知下我，tks (63) JiaJunpeng 2014-02-07 14:52:36
  • Re:想做但又没时间，提供个思路，谁ac了通知下我，tks (123) JiaJunpeng 2014-02-07 17:33:38