HBC19887[AHOI2009]MINCUT 最小割题解（最小代价路径切断方案）

八贝勒算法基础篇 2023-11-09 05:14:02 38 0

想要成为编程高手？那就来试试全网最全C++题库，让您在练习中快速成长。

现在请你回答这两个问题。

A,B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路。设其中第i (1 ≤ i ≤ M)条道路连接了vi,ui两个中转站，那么中转站vi可以通过该道路到达ui中转站，如果切断这条道路，需要代价ci。现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小。小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题：问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？现在请你回答这两个问题。