什么样的网站利于百度优化,专业建站教程,建设网站审批,学做烤制食品的网站传送门 引入两个概念#xff1a; 最小点权覆盖集#xff1a;满足每一条边的两个端点至少选一个的最小权点集。 最大点权独立集#xff1a;满足每一条边的两个端点最多选一个的最大权点集。 现在对网格染色#xff0c;使得相邻两点颜色不同#xff0c;之后把两个颜色的点分…传送门 引入两个概念 最小点权覆盖集满足每一条边的两个端点至少选一个的最小权点集。 最大点权独立集满足每一条边的两个端点最多选一个的最大权点集。 现在对网格染色使得相邻两点颜色不同之后把两个颜色的点分成两个集合X,Y。S向X集合每个点连一条该点权值的边Y集合每个点向T连一条该点权值的边原来的边流量全部变为INF。这个网络的最小割为最小点权覆盖集。因为这个最小割满足了对于中间每一条边两端的点必定选择了一个。若一个都没有选择则S与T仍连通。且因为中间的边流量为INF所以不会是中间被堵塞。 然后我们可以证明对于每一个点权覆盖集将选的点不选不选的点选得到的点集一定是一个点权独立集。因为每一条边至少选了一个反选后就至少有一个选不了。 所以该网络的最小割最大流权值和-答案 答案就是权值和-最大流跑一遍最大流即可 ——代码 1 #include queue2 #include cstdio3 #include cstring4 #include iostream5 #define INF 1e96 #define N 100107 #define M 500018 #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] {0, 1, -1, 0}, dy[4] {1, 0, 0, -1};13 14 inline int read()15 {16 int x 0, f 1;17 char ch getchar();18 for(; !isdigit(ch); ch getchar()) if(ch -) f -1;19 for(; isdigit(ch); ch getchar()) x (x 1) (x 3) ch - 0;20 return x * f;21 }22 23 inline void add(int x, int y, int z)24 {25 to[cnt] y;26 val[cnt] z;27 next[cnt] head[x];28 head[x] cnt;29 }30 31 inline bool bfs()32 {33 int i, u, v;34 std::queue int q;35 memset(dis, -1, sizeof(dis));36 q.push(s);37 dis[s] 0;38 while(!q.empty())39 {40 u q.front(), q.pop();41 for(i head[u]; i ^ -1; i next[i])42 {43 v to[i];44 if(val[i] dis[v] -1)45 {46 dis[v] dis[u] 1;47 if(v t) return 1;48 q.push(v);49 }50 }51 }52 return 0;53 }54 55 inline int dfs(int u, int maxflow)56 {57 if(u t) return maxflow;58 int v, d, ret 0;59 for(int i cur[u]; i ^ -1; i next[i])60 {61 v to[i];62 if(val[i] dis[v] dis[u] 1)63 {64 d dfs(v, min(val[i], maxflow - ret));65 ret d;66 val[i] - d;67 val[i ^ 1] d;68 if(ret maxflow) return ret;69 }70 }71 if(ret ^ maxflow) dis[u] -1;72 return ret;73 }74 75 int main()76 {77 int i, j, k, x, y;78 m read();79 n read();80 s 0, t n * m 1;81 memset(head, -1, sizeof(head));82 for(i 1; i m; i)83 for(j 1; j n; j)84 {85 num;86 sum x read();87 if((i j) 1)88 {89 add(s, num, x), add(num, s, 0);90 if(i 1) add(num, num - n, INF), add(num - n, num, 0);91 if(i m) add(num, num n, INF), add(num n, num, 0);92 if(j 1) add(num, num - 1, INF), add(num - 1, num, 0);93 if(j n) add(num, num 1, INF), add(num 1, num, 0);94 }95 else add(num, t, x), add(t, num, 0);96 }97 while(bfs())98 {99 for(i s; i t; i) cur[i] head[i];
100 sum - dfs(s, INF);
101 }
102 printf(%d\n, sum);
103 return 0;
104 } View Code 转载于:https://www.cnblogs.com/zhenghaotian/p/6936100.html
