[理工] 103中央算法 bobo1004 PTT批踢踢实业坊

[理工] 103中央算法

楼主: bobo1004 (boboL) 2020-12-10 19:51:26

https://imgur.com/jomcR7j
https://imgur.com/fAd1SvM
https://imgur.com/sefXczV
想请问大大们
第5题(1) 可以直接写用DFS从第1个开始跑, 当侦测到back edge时, 则代表有cycle 吗?
第5题(2)(3)还有第7题求指点 @д@

作者: aa871220 (TMVP_Yueko) 2020-12-10 20:24:00

1 你解法很怪这样要额外先建link list再DFS不是说不行更直觉作法是直接disjoint set 每次捞一笔资料确认findset(u)!=findset(v)然后加进set C中若findset(u)=findset(v)即有cycle或input行数不等于n-1也会不构成Tree更正是union 不是加进set C

楼主: bobo1004 (boboL) 2020-12-10 20:58:00

https://imgur.com/9LyPuFB a大是这样写吗?

作者: mathtsai (mathtsai) 2020-12-10 21:11:00

(1)有back edge代表有cycle(2)用greedy证明

作者: aa871220 (TMVP_Yueko) 2020-12-10 22:44:00

是

楼主: bobo1004 (boboL) 2020-12-11 00:22:00

m大请问你怎用Greedy做,a大那能问你其他两题吗?

作者: mathtsai (mathtsai) 2020-12-11 01:56:00

假如有个最好的选法不选edge(u,v)你可以把matching给u的点换成v 这样就和最好的做法一样可以google "tree maximum matching"

继续阅读

[理工] 100 交大 Floyd-Warshall 负weight cyclebooowei1203 [理工] 线代函数唯一性aa871220 [理工] 107台大电机离散（6）（11）jimmylin1024 [理工] 计组（下）p.175sososlee [理工] 108 台大电机丙复选题joywilliamjo [理工] 线代 rank相关 109清大数学ff00662299 [理工] 考古题作业系统Race condition LaLaplace [理工] 106 台大电机丙资结joywilliamjo [理工] 离散成大108数学try66889 [理工] 108 交大资演 reductionaa871220

[理工] 103中央 算法

[理工] 103中央算法