19_04_25校内训练[最小割]
题意
给出有向图，有边权。选择一些边，使得所有从1到n的每条路径（可重复经过点和边）都经过了选中边恰好一条，求最小代价。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
思考
首先缩点，因为一个强连通分量中的边可以重复经过，一定不会选。
若限制是至少经过一条，则是最小割模型。
考虑最小割的意义。它将点集分为S和T集，使得割去所有S集到T集中的边后，原图不连通且代价最小。
那何时路径会重复经过选中的边？当且仅当T集有边连向S集。
![19_04_25校内训练[最小割] 随笔](https://img.liuyixiang.com/image/2019/4/ERZbya.png "19_04_25校内训练[最小割] 随笔")
这种情况下，就要强制红色的边一定有从S集连向T集的边，在下一次一定会被去掉。
那就将反向边设置为inf，这样不合法的路径就会被拆掉。最小割即可。
Trick：一开始要删掉1走不到的点。正确性显然。
更多精彩
