最小割题解1
需积分: 0 80 浏览量
2022-08-03
11:14:44
上传
评论
收藏 228KB PDF 举报
POJ2914【基础】
题目大意：
给出一个有权无向图，求其最小割。
输入：
有若干组测试数据。每一组测试数据的前两行有两个整数 N 和 M，表示有 N 个
点（依次编号为 1 到 N）和 M 条边（2<=N<=500，1<=M<=(N-1)*N/2）。接下来
有 M 行，每一行有三个整数 A、B 和 C，表示 A 和 B 之间有一条容量为 C 的边。
两组测试数据之间没有空行。
输出：
对于每一组测试数据，输出一行，包含一个整数，即其最小割的。如果图不连
通，输出 0。
题解：
这题我用来做了我的 Stoer-Wagner 算法模板，是从
http://blog.sina.com.cn/s/blog_6635898a0100qwd0.html 的第一个模板改过
来的。顺带一提，这篇文章后面的那个模板跑了 8000+ms，第一个模板跑了
3100+ms……
POJ2125【基础】
题目大意：
给出一张图，有 N 个顶点和 M 条有向边。每一次可以取走一个点和它的所有出
边，或者一个点和它的所有入边。对于 i 点，取走所有入边的代价为 Wi+，取
走所有出边的代价为 Wi-。求删除图中所有边的最小代价。
输入：
输入的第一行包含两个整数 N 和 M（1<=N<=100，1<=M<=5000）。第二行有 N 个
整数，依次为 W1+到 WN+。第三行有 N 个整数，依次为 W1-到 WN-。接下来有 M
行，每一行有两个整数 u、v，表示有一条有向边从 u 指向 v。
输出：
评论0