傳送門
?
引入兩個概念：
最小點權覆蓋集：滿足每一條邊的兩個端點至少選一個的最小權點集。
最大點權獨立集：滿足每一條邊的兩個端點最多選一個的最大權點集。
現在對網格染色，使得相鄰兩點顏色不同，之后把兩個顏色的點分成兩個集合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] = {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 }
?
方法詳解)
)
