（FJWC2020）DTOJ 4679. 赢家

本文主要是介绍（FJWC2020）DTOJ 4679. 赢家，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给定一个$n$个点$m$条边的无向图，给每一条边定向，使得存在一个点，1号点和2号点能同时到达，求边定向的方案数。
$n\le 15$

题解

暴力做法就是枚举每条边的方向，判断1号点和2号点能走到的点集是否有交集。
发现有交集是不好直接计数的，考虑容斥：总方案数减去无交集的方案数。于是预处理出1号点和2号点分别能到达极大的每个集合的方案数，枚举它们到达的极大集合$a,b$，判断是否有连接$a$和$b$的边，若有则一定能到达，不考虑即可；否则减去这样的方案数。
感觉思路很自然，也不知道考场上在干什么。

这篇关于（FJWC2020）DTOJ 4679. 赢家的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---