每个点的流量也要控制呢QwQ
by vicky128 @ 2023-07-07 19:20:00
@[oiyang](/user/856309)
by vicky128 @ 2023-07-07 19:20:08
额那个刚刚自己学网络流，还有些不太明白。为什么这么建边可以控制流量？qaq
by oiyang @ 2023-07-07 19:27:19
@[ESCAP1ST404](/user/284754)
为啥
by oiyang @ 2023-07-07 19:54:01
@[oiyang](/user/856309) 给书建边的时候要控制**每本书只被配对了至多一次**，因此把书拆成两个点，在两个点之间连一条容量为 $1$ 的有向边，最后把两个点分别与练习册和答案相连（容量均为 $1$）。这样求解最大流的时候就能够保证通过这本书的流量最多为 $1$，从而保证每本书只被配对了至多一次。
by escapist404 @ 2023-07-07 19:57:52
就是s到练习册他是直接连边，然后书拆成n1+book 和 n2+n1+book ，那为什么在连答案的时候要搞成n2+n1+n1+answer?
by oiyang @ 2023-07-07 20:02:19
@[ESCAP1ST404](/user/284754)
by oiyang @ 2023-07-07 20:03:14
@[oiyang](/user/856309) 没看懂你说的连答案是什么意思，但是这个就是s->练习册->书->书->答案,但是要保证每个点都是单独的，就可以让两次书分别是[1,n1],和[n1+n2+n3+1,n1+n2+n3+n1],练习册：[n1+1,n2],答案[n2+1,n3]，远点汇点随便就好了
by czrq @ 2023-12-29 17:36:32