Difference between revisions of "2019 Multi-University,HDU Day 3"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
| Line 7: | Line 7: | ||
Solved by Xiejiadong && Wwaver_zhu. 01:59:02 (+1) | Solved by Xiejiadong && Wwaver_zhu. 01:59:02 (+1) | ||
| − | + | 题意：给出一个 DAG ，每次询问两个点，求有多少方案通过删除一个点，使得其中一个点无法到达所有他所在的联通块出度为 $0$ 的点。 | |
| + | |||
| + | 题解：把所有出度为 $0$ 的点连向一个超级汇点，显然，询问就变成了任意一个点无法到达超级汇点的方案。 | ||
| + | |||
| + | 以超级汇点作为起点，建反图，那么，可以删除的点就一定是从超级汇点出发到询问点的必经点。 | ||
| + | |||
| + | 在支配树上，方案树就是询问的两个点的祖先的并，求个 lca 就好了。 | ||
== Problem C == | == Problem C == | ||
Revision as of 08:55, 29 July 2019
Problem A
Unsolved.
Problem B
Solved by Xiejiadong && Wwaver_zhu. 01:59:02 (+1)
题意：给出一个 DAG ，每次询问两个点，求有多少方案通过删除一个点，使得其中一个点无法到达所有他所在的联通块出度为 $0$ 的点。
题解：把所有出度为 $0$ 的点连向一个超级汇点，显然，询问就变成了任意一个点无法到达超级汇点的方案。
以超级汇点作为起点，建反图，那么，可以删除的点就一定是从超级汇点出发到询问点的必经点。
在支配树上，方案树就是询问的两个点的祖先的并，求个 lca 就好了。
Problem C
Unsolved.
Problem D
Unsolved.
Problem E
Unsolved.
Problem F
Solved by Kilo_5723 && Weaver_zhu. 00:33:20 (+1)
Problem G
Solved by Xiejiadong. 00:41:23 (+1)
Problem H
Unsolved.
Problem I
Solved by Xiejiadong && Wwaver_zhu. 04:33:20 (+4)
Problem J
Unsolved.
Problem K
Unsolved.