inline">\(0/1\)选择和一些约束条件，求出一组满足所有条件的解

---

inline">\(0/1\)选择的性质

如果

都是在两者中选其一，不难想到我们可以建立两个相互对立的点来表示限制。

inline">\(dinic\)，我们可以得到一个时间复杂度为

inline">\(O(m\sqrt{n})\)

现在连的边代表限制，这样的边并不能满足图论中最基础的性质：传递性。

例如：对于

inline">\(a,b\)不在一个集合，以及

class="math

inline">\(b,c\)不在一个集合，但我们不能得到

class="math

inline">\(a,c\)一定在同一个集合，因为

inline">\(ai,0,ai,1\)其中一个不选，那么另一个一定要选。

那么我们就可以把先前的图重构，即

对于

inline">\(∀(ax,y,az,w)∈E\)连接

class="math

inline">\((ax,y,az,w')\)，若

class="math

inline">\(w'=0\)；反之亦然

注意：同一个

inline">\(a_{x,0},a_{x,1}\)之间不再需要连边，因为这种边在新图中以自环的形式存在，因此不再在之后的操作中不再考虑。

这样边

inline">\((u,v)\)的实际意义为选了

class="math

inline">\(v\)。

这样便就满足传递性了。

那这样有什么好处呢？

注意到对于有向图中的一个强连通分量（即对于强连通分量中的每个点都能将自己

选择的状态传递给强连通分量中的任意一个点），因此强连通分量中每个点的状态都相同。

都在同一个连通块，即同时都要选或同时都不选，就会产生矛盾

这时已经没有边

inline">\((ax,0,ax,1)\)，只有边

inline">\((ax,0,ax,0),(ax,1,ax,1)\)

class="math

inline">\(tarjan\)来将强连通分量缩点，再用拓扑排序，求出一组可行方案