> 两幅树形图，其实就是除了源点之外，所有点都有两条入边，有任意多的出边，基于这个性质，构造网络流模型。
> 
> 于是拆点，x拆成x与x'
> 
> 添加源汇s, t
> s连到所有x，容量无穷大
> 所有x'连到汇，容量为2
> 
> 如果有边a->b
> 则连边a->b'，容量为1
> 
> 求最大流，如果总流量为2n-2，则有解
> 每个点都有两条流流入，也就是树形图中的两个入边
> 
> 输出解很容易，对于每个点，任选一条入边，这样就构造了第一幅树形图；剩下的肯定是另外一幅树形图
> 
> 题目还蛮有新意，让人想做，就是描述太麻烦了
> 
> 按这个思路这个题应该不难才对，但不明白为什么1人ac，没时间做acm了，有人这样ac了pm一下

• 我没有说不是啊，你没看明白？ (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