传送门
引入两个概念：
最小点权覆盖集：满足每一条边的两个端点至少选一个的最小权点集。
最大点权独立集：满足每一条边的两个端点最多选一个的最大权点集。
现在对网格染色，使得相邻两点颜色不同，之后把两个颜色的点分成两个集合X,Y。S向X集合每个点连一条该点权值的边，Y集合每个点向T连一条该点权值的边，原来的边流量全部变为INF。这个网络的最小割为最小点权覆盖集。因为这个最小割满足了，对于中间每一条边，两端的点必定选择了一个。若一个都没有选择则S与T仍连通。且因为中间的边流量为INF所以不会是中间被堵塞。
然后我们可以证明对于每一个点权覆盖集，将选的点不选，不选的点选，得到的点集一定是一个点权独立集。因为每一条边至少选了一个，反选后就至少有一个选不了。
所以该网络的最小割=最大流=权值和答案
答案就是权值和最大流，跑一遍最大流即可
——代码
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define INF 1e9 6 #define N 10010 7 #define M 50001 8 #define min(x, y) ((x) < (y) ? (x) : (y)) 9 10 int n, m, cnt, sum, s, t, num; 11 int head[N], to[M], val[M], next[M], dis[N], cur[N]; 12 int map[101][101], dx[4] = , dy[4] = ; 13 14 inline int read() 15 22 23 inline void add(int x, int y, int z) 24 30 31 inline bool bfs() 32 50 } 51 } 52 return 0; 53 } 54 55 inline int dfs(int u, int maxflow) 56 70 } 71 if(ret ^ maxflow) dis[u] = 1; 72 return ret; 73 } 74 75 int main() 76 95 else add(num, t, x), add(t, num, 0); 96 } 97 while(bfs()) 98 102 printf("%d\n", sum); 103 return 0; 104 }View Code
上一篇：[luoguP2870] [USACO07DEC]最佳牛线，黄金Best Cow Line, Gold（后缀数组）
下一篇：[luoguP2758] 编辑距离（DP）
最大流 网络流 最大独立集 最小点覆盖 最小割
