首页 > 代码库 > HDU3657Game（最大流）
HDU3657Game（最大流）
这几天敲了几道最大流的问题，发现网络流真是模板算法啊。。。。
敲来敲去敲了几遍，基本每遍都敲得让人灰心，但同时也感受到了网络流的强大所在，这是我做网络流的第一题，，本以为看了一遍小白书的代码差不多理解就可以A掉一题的，没想到打击不是一点点的少啊。。。。。
首先小白书将的邻接矩阵存边，这里必须用邻接表，而本以为随便改改就好的，没想到那个记录路径却让人头疼得要命，无赖之下看了题解，看到了一个名为SAP的强大算法，虽然比小白的代码量增加了不少，理解起来也不是很容易，但是复杂度真心减少了不知一点点啊！！！！
虽然履步维艰，最后慢慢看着大牛模板一点一点敲了出来，可是其实还不是特别的了解的说，只是大致明白了思路而已，没办法看不懂就背下来吧，相信敲得多了自然就会慢慢理解记住的。。。
下面的SAP代码风格是我在网上找了一些后自己最觉得满意的一种（看到很多人使用loop；goto语句，真心不想用那样的句子啊，真心强迫症患者啊。。。。）
(能有自己的网络流模板感觉真好~~~)
1 #include <map> 2 #include <set> 3 #include <stack> 4 #include <queue> 5 #include <cmath> 6 #include <ctime> 7 #include <vector> 8 #include <cstdio> 9 #include <cctype> 10 #include <cstring> 11 #include <cstdlib> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 #define INF 0x3f3f3f3f 16 #define inf ((LL)1<<40) 17 #define lson k<<1, L, mid 18 #define rson k<<1|1, mid+1, R 19 #define mem0(a) memset(a,0,sizeof(a)) 20 #define mem1(a) memset(a,-1,sizeof(a)) 21 #define mem(a, b) memset(a, b, sizeof(a)) 22 #define FOPENIN(IN) freopen(IN, "r", stdin) 23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 24 template<class T> T ABS ( T a) { return a >= 0 ? a : -a; } 25 template<class T> T CMP_MIN ( T a, T b ) { return a < b; } 26 template<class T> T CMP_MAX ( T a, T b ) { return a > b; } 27 template<class T> T MAX ( T a, T b ) { return a > b ? a : b; } 28 template<class T> T MIN ( T a, T b ) { return a < b ? a : b; } 29 template<class T> T GCD ( T a, T b ) { return b ? GCD ( b, a % b ) : a; } 30 template<class T> T LCM ( T a, T b ) { return a / GCD ( a, b ) * b; } 31 template<class T> void SWAP( T& a, T& b ) { T t = a; a = b; b = t; } 32 33 typedef __int64 LL; 34 //typedef long long LL; 35 const int MAXN = 101000; 36 const int MAXM = 500100; 37 const double eps = 1e-14; 38 const double PI = 4.0 * atan(1.0); 39 const LL MOD = 1000000007; 40 41 int dx[4] = {0, -1, 0, 1}; 42 int dy[4] = {1, 0, -1, 0}; 43 44 int n, m, k, ma[55][55], mus[55][55], sum; 45 46 struct Edge { int to, cap, next; }edge[MAXM<<1]; 47 int head[MAXN], tot; 48 49 int src, des; 50 int dep[MAXN], gap[MAXN], pre[MAXN], aug[MAXN], cur[MAXN]; 51 52 void init() 53 { 54 int x, y; 55 mem0(mus); mem0(edge);sum = 0; 56 for(int i = 1; i <= n; i ++) 57 { 58 for(int j = 1; j <= m; j ++ ) 59 { 60 scanf("%d", &ma[i][j]); 61 sum += ma[i][j]; 62 } 63 } 64 for(int i = 0; i < k; i ++) 65 { 66 scanf("%d %d", &x, &y); 67 mus[x][y] = 1; 68 } 69 } 70 71 void addEdge(int u, int v, int val) 72 { 73 edge[tot].to = v; edge[tot].cap = val; edge[tot].next= head[u]; 74 head[u] = tot ++; 75 edge[tot].to = u; edge[tot].cap = 0; edge[tot].next = head[v]; 76 head[v] = tot ++; 77 } 78 79 void init_Edge() 80 { 81 mem1(head); tot = 0; 82 src = http://www.mamicode.com/0; des = m * n + 1; 83 for(int i = 1; i <= n; i ++) 84 { 85 for(int j = 1; j <= m; j ++) 86 { 87 int now = (i-1)*m + j; 88 if((i+j)&1){ 89 if(mus[i][j]) addEdge(now, des, INF); 90 else addEdge(now, des, ma[i][j]); 91 } 92 else { 93 if(mus[i][j]) addEdge(src, now, INF); 94 else addEdge(src, now, ma[i][j]); 95 for(int k = 0; k < 4; k ++ ) { 96 int nx = i + dx[k], ny = j + dy[k]; 97 if(nx>0 && nx<=n && ny>0 && ny<=m) 98 addEdge(now, (nx-1)*m+ny, 2*(ma[i][j]&ma[nx][ny])); 99 }100 }101 }102 }103 }104 105 int SAP(int n)106 {107 mem0(aug); mem0(pre);108 mem(dep, 0); mem(gap, 0);109 int max_flow = 0, u = src;110 aug[src] = INF;111 pre[src] = -1;112 gap[0] = n;113 for(int i = 0; i <= n; i ++)114 cur[i] = head[i];115 while(dep[src] < n)116 {117 //printf("%d\n", u);118 if(u == des)119 {120 // printf("%d\n", max_flow);121 max_flow += aug[des];122 for(int v = pre[des]; v != -1; v = pre[v])123 {124 int e = cur[v];125 edge[e].cap -= aug[des];126 edge[e^1].cap += aug[des];127 aug[v] -= aug[des];128 if(edge[e].cap == 0) u = v;129 //u = src;130 }131 }132 int flag = 0;133 for(int e = cur[u]; e != -1; e = edge[e].next)134 {135 int v = edge[e].to;136 if(edge[e].cap > 0 && dep[u] == dep[v] + 1)137 {138 flag = 1;139 pre[v] = u; cur[u] = e;140 aug[v] = MIN(aug[u], edge[e].cap);141 u = v;142 break;143 }144 }145 if(!flag)146 {147 if(--gap[dep[u]] == 0)148 break;149 int min_dep = n;150 cur[u] = head[u];151 for(int e = head[u]; e != -1; e = edge[e].next)152 {153 int v = edge[e].to;154 if(edge[e].cap > 0 && dep[v] < min_dep)155 {156 min_dep = dep[v];157 cur[u] = e;158 }159 }160 dep[u] = min_dep + 1;161 gap[dep[u]] ++;162 if(u != src) u = pre[u];163 }164 }165 return max_flow;166 }167 168 int main()169 {170 while(~scanf("%d %d %d", &n, &m, &k))171 {172 init();173 init_Edge();174 printf("%d\n", sum - SAP(des+1));175 }176 return 0;177 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。