Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

请问一下,能保证树的有向性吗?

Posted by tomorrow911 at 2009-08-29 14:52:42 on Problem 3745
In Reply To:想做但又没时间,提供个思路,谁ac了通知下我,tks Posted by:majia_ at 2009-08-26 17:31:39
> 两幅树形图,其实就是除了源点之外,所有点都有两条入边,有任意多的出边,基于这个性质,构造网络流模型。
> 
> 于是拆点,x拆成x与x'
> 
> 添加源汇s, t
> s连到所有x,容量无穷大
> 所有x'连到汇,容量为2
> 
> 如果有边a->b
> 则连边a->b',容量为1
> 
> 求最大流,如果总流量为2n-2,则有解
> 每个点都有两条流流入,也就是树形图中的两个入边
> 
> 输出解很容易,对于每个点,任选一条入边,这样就构造了第一幅树形图;剩下的肯定是另外一幅树形图
> 
> 题目还蛮有新意,让人想做,就是描述太麻烦了
> 
> 按这个思路这个题应该不难才对,但不明白为什么1人ac,没时间做acm了,有人这样ac了pm一下

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator