SYOI 2022 Round 2 Editorial
SYOI2022 Round2 LinkTask 1
使用网络流最小割。
考虑建图：将原矩阵黑白染色，黑格连源点，白格连汇点，弧容量为方格中的数。
为了让最小割满足题目中的含义，还要将相邻的黑白格连一条容量为无穷的边。
这样，为了让图不连通，就必须要割掉一些边，最小割可以求出来最小花费。
用总和减去最小割即可。
CODE
#include #include #include #include const int INF = 0x3f3f3f3f;const int maxn = 35;int fx[] = {0 , -1 , 0 , 1},fy[] = {1 , 0 , -1 , 0};using namespace std;struct edge { int to,next,cap; edge() { to = next = cap = 0; } edge(int to,int next,int cap):to(to),next(next),cap(cap){}}Edge;int head[maxn * maxn = 1&&x = 1&&y
页:
[1]