[luoguP2774] 方格取数问题（最大点权独立集）

传送门

引入两个概念：

最小点权覆盖集：满足每一条边的两个端点至少选一个的最小权点集。

最大点权独立集：满足每一条边的两个端点最多选一个的最大权点集。

现在对网格染色，使得相邻两点颜色不同，之后把两个颜色的点分成两个集合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

上一篇：[luoguP2763] 试题库问题（最大流）

下一篇：[luoguP2770] 航空路线问题（最小费用最大流）

---

最小点覆盖 最大流 最小割 网络流 最大独立集