Day -9
gp终于开网了，做了几道zsq给的题
luoguP4306:
一开始看到这题觉得复杂度最少是\(\frac{n^3}{w}\) ，尝试优化了一下，结果发现优化不了，觉得不可做，一看题解，正解竟然真是\(\frac{n^3}{w}\) ，出题人开2000是不是有病啊。
luoguP1407:
这题一眼觉得是割边，结果发现是错的。
考虑对于原来的婚姻关系让男的连女的，后面给的关系让女的连男的，这样断掉一条关系的时候只要看一下从女的开始遍历能不能遍历回男的就行了，很明显是一个强连通，缩点后看男的和女的在不在一个点就行了。
luoguP4819:
又是令人窒息的概率题
认真考虑一下发现并不是很难，先把强连通分量都缩点，问一个点可以把它能遍历到的点都遍历完，明显的贪心去问入度为0的点，但是还要考虑排除法，如果只有一个点还没确定，那它必为杀手，判断一下就行了。
luoguP2515:
考虑存反边，很明显对于一个环只有全部都安装才有贡献，直接缩点，因为每个点入度只为1，所以肯定是一颗树，直接树上背包就行了。