Andrew and Taxi

$\mathrm{问}\mathrm{题}\mathrm{是}\mathrm{求}\mathrm{一}\mathrm{个}\mathrm{有}\mathrm{向}\mathrm{图},\mathrm{可}\mathrm{以}\mathrm{修}\mathrm{改}\mathrm{边}\mathrm{的}\mathrm{方}\mathrm{向},\mathrm{要}\mathrm{求}\mathrm{修}\mathrm{改}\mathrm{的}\mathrm{最}\mathrm{大}\mathrm{值}\mathrm{最}\mathrm{小}\mathrm{使}\mathrm{得}\mathrm{图}\mathrm{无}\mathrm{环}问题是求一个有向图,可以修改边的方向,要求修改的最大值最小使得图无环$

首先对于最大值最小可以考虑二分,至于$ckck$的话,我们对于边的权值小于二分值$uu$的都可以缩成$w>uw>u$上的一点,这是显然的,然后呢,只要从小到大连接/从大到小连接即可.检测有没有环只要判断边权>$ww$的是否能被$DAGDAG$图遍历到即可.

code:

https://codeforces.com/contest/1100/submission/151292473