2022/07/17 做题记录

CF1369F

发现当所有点权值小于度数时一定无解,考虑最后一条删的边,当删除它时它的两个端点权值一定都是 0。

于是找到一个权值大于等于度数的点,发现即使所有连到它的边都依靠它来删,也是一定合法的,于是把它的所有连接它的边删掉,因为这个点已经发挥了最大可能的贡献,所以如果原图有解,删后的图也一定有解。

于是直接一个一个删知道把点删完或判定无解即可。

写的 O(nlogn)O(n \log n),没仔细想 O(n)O(n)

code: https://codeforces.com/contest/1369/submission/164574089