最近学了下费用流，然后又从网上听说了传纸条可以用费用流完成，于是就试了一下。结果调了半天终于通过了。其原理很简单，就是在图中求两条不相交路径，使途经点权和最大。方法就是把原图中的每个点x拆成x1和x2，对于每个点x和它右面或者下面的点y，建立起止点为x2,y1,费用为0,流量为1的边。并且建立起止点为x1,x2,费用为点权，流量为1的边。特别地，起点（1,1）和终点（n,m）点内的边流量应为2.然后求图的最大费用最大流即可。
一直在费用流增广那里卡了很久……总是报SISEGV，后来发现条件应该是i!=S而不是i!=0，然后就A了。这种方法比DP高效，但是代码长度和思维难度…………所以这种方法对于NOIP来说，简直是高射炮打蚊子。
View Code 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int inf = 0x3f3f3f3f; 8 const int maxn = 5010; 9 const int maxm = 20010; 10 struct Node { 11 int end, val, cost; 12 Node *next, *op; 13 }edge[maxm], *head[maxn], *p, *fe[maxn]; 14 int S, T, n, m, ans; 15 int dist[maxn], que[maxn], ft[maxn]; 16 bool inq[maxn]; 17 18 inline int bh(int i, int j, int flag) { 19 return ((i - 1) * m + j) * 2 + flag - 1; 20 } 21 inline void add_edge(int a, int b, int v, int co) { 22 p ++; 23 p -> end = b; 24 p -> val = v; 25 p -> cost = co; 26 p -> next = head[a]; 27 head[a] = p; 28 p ++; 29 p -> end = a; 30 p -> val = 0; 31 p -> cost = -co; 32 p -> next = head[b]; 33 head[b] = p; 34 head[a] -> op = head[b]; 35 head[b] -> op = head[a]; 36 } 37 inline void init() { 38 p = edge; int fy; 39 scanf("%d%d", &n, &m); 40 S = 1, T = n * m * 2; 41 for (int i = 1; i <= n; i ++) 42 for (int j = 1; j <= m; j ++) { 43 scanf("%d", &fy); 44 if (i == 1 && j == 1) { 45 add_edge(bh(1, 1, 0), bh(1, 1, 1), 2, 0); 46 } else if (i == n && j == m){ 47 add_edge(bh(n, m, 0), bh(n, m, 1), 2, 0); 48 } else { 49 add_edge(bh(i, j, 0), bh(i, j, 1), 1, fy); 50 } 51 if (j < m) add_edge(bh(i, j, 1), bh(i, j + 1, 0), 1, 0); 52 if (i < n) add_edge(bh(i, j, 1), bh(i + 1, j, 0), 1, 0); 53 } 54 } 55 inline bool spfa() { 56 for (int i = S; i <= T; i ++) 57 dist[i] = -inf; 58 dist[S] = 0; 59 int open = 0, close = 0; 60 que[++ open] = S; inq[S] = true; 61 while (open != close) { 62 close ++; close %= maxn; 63 int t = que[close]; inq[t] = false; 64 for (Node *p = head[t]; p; p = p -> next) { 65 int end = p -> end; 66 if (p -> val && dist[t] + p -> cost > dist[end]) { 67 dist[end] = dist[t] + p -> cost; 68 ft[end] = t; 69 fe[end] = p; 70 if (!inq[end]) { 71 open ++; open %= maxn; 72 que[open] = end; inq[end] = true; 73 } 74 } 75 } 76 } 77 return dist[T] != -inf; 78 } 79 inline void augment() { 80 int min_f = inf; 81 for (int i = T; i != S; i = ft[i]) 82 min_f = min(min_f, fe[i] -> val); 83 for (int i = T; i != S; i = ft[i]) { 84 fe[i] -> val -= min_f; 85 fe[i] -> op -> val += min_f; 86 ans += min_f * fe[i] -> cost; 87 } 88 } 89 inline int work() { 90 ans = 0; 91 while (spfa()) 92 augment(); 93 return ans; 94 } 95 int main() { 96 init(); 97 printf("%d\n", work()); 98 return 0; 99 }转载于:https://www.cnblogs.com/stickjitb/archive/2012/11/18/2775793.html
