最小割

51Nod 1499 图

Posted on

emmmmmmm不错的的最小割吧
唯一一个不是很好的点就是实在是太容易想到是最小割了,但是没想到具体的建图方法。

题意:
有n个点,m条边,要你分成两个集合,使得两个集合的导出子图各自权值和的和最大。
两个导出子图中,可选择其中一个,若导出子图中存在有两个点 (i,j) 相连,则该导出子图权值增加 $| i-j |$ 。同时另一个导出子图则相反,只有存在两个点没有边相连,才会增加权值。

思路:
题目的主要目的就是将点集分成两部分,这很容易想到二分图染色,但这是不现实的,因为这是一个最值问题,不存在必然关系。
而跟二分图相关的只有网络流了,将图分为两半是割的概念,当然只存在最小割,正面去想的话,就是总权值和-最小割。

然后……思路就断了,找不到有效的建图方法。

可以先这么想,我们假定与源点相连的点集为相连增加权值的集合,并称之为,与汇点相连的点集则相反,称之为汇点集。
那么我们先将每个点都与源点相连,其容量为将该点加入源点集所能增加的权值。
再将这个点与汇点相连,其容量为将该点加入汇点集所能增加的权值。

此时直接跑最小割是不对的,因为这些点并不是独立的。

其实只要再将任意两个点都连边就可以了。

啊,顺便发现一个,换一种无向图建边,速度快了一倍,因为边几乎少了一半

AC Code

#include <cstdio>
#include <cstring>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 1e3 + 5;
const int maxm = 5e6 + 5;
const int inf = 0x3f3f3f3f;

int src, des, idx;
int cur[maxn], level[maxn], head[maxn];

struct node {
    int to, next;
    int cap;
    node() {}
    node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm << 1];

queue<int> que;

void addEdge(int u, int v, int c, int rc = 0)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], rc);//无向边建边小技巧
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que.push(src);
    level[src] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].next) {
            int v = edges[id].to;
            if (edges[id].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[des] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == des)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].next) {
        int v = edges[id].to;
        if (edges[id].cap > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].cap)))) {
            edges[id].cap -= cflow;
            edges[id ^ 1].cap += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic(int n)
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= n + 1; i++)
            cur[i] = head[i];
        while ((cflow = dfs(src, inf)))
            ans += cflow;
    }
    return ans;
}

void init(int s, int d)
{
    memset(head, -1, sizeof head);
    idx = 0;
    src = s, des = d;
}

bool g[maxn][maxn];
int s[maxn], t[maxn];

inline void scan_d(int& num)
{
    char in;
    in = getchar();
    while (in != '-' && (in < '0' || in > '9'))
        in = getchar();
    num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') {
        num *= 10, num += in - '0';
    }
}

int main()
{
    int n, m, u, v, tmp;
    scan_d(n), scan_d(m);
    init(0, n + 1);
    while (m--) {
        scan_d(u), scan_d(v);
        g[u][v] = g[v][u] = true;
    }
    range(i, 1, n) range(j, i + 1, n)
    {
        tmp = j - i;
        if (g[i][j])
            s[i] += tmp, s[j] += tmp;
        else
            t[i] += tmp, t[j] += tmp;
        addEdge(i, j, tmp, tmp);
    }
    int ans = 0;
    range(i, 1, n) addEdge(src, i, s[i]), addEdge(i, des, t[i]);
    range(i, 1, n) ans += (1 + n - i) * (n - i) / 2;
    printf("%d\n", ans - dinic(n) / 2); //因为与源点汇点相连的点增加了一倍权值
    return 0;
}
最小割

HihoCoder 1252 Kejin Game

Posted on

网络流建图神题!!!
同时也是2015年北京现场赛的金牌题,虽然我不可能去挑战金牌,但是也只有做这种神题,尽管不是自己想得,但A了之后仍然充满了满足。

题意:
给你一个DAG,表示一个游戏的技能树,也就是说某一些技能存在前置技能,但实际上这是为氪金大佬准备的游戏,有钱是真的可以为所欲为的,大佬们可以选择花钱直接无视所有前置技能直接习得某一个技能,也可以消除掉两个技能之间的依赖关系。

现在某个节俭的大佬想要学某一个技能,问最小花费。

思路:
说实话这道题一眼真的很容易想到图上DP,但是存在可以消除一个依赖的权利,使得DP存在后效性。
正解是最小割建模,这个最小割建模真的是非常巧妙:

  1. 拆点建图,u -> u' 的容量是直接氪金习得这一技能的花费
  2. 如果u,v存在依赖关系 u -> v ,建边 u' -> v ,容量为消除这个依赖的费用
  3. 将源点与每一个技能连边,容量为按技能树学习的费用。
  4. 将所要求的技能与汇点相连,容量为 inf

最后跑一遍最大流就是答案。

网上很多题解到这里就没了,也没有一个像样点的解释。

对于学习技能来说,其实就是一个消除依赖的过程,当然你不氪金的话还要花费学习这个技能份额费用,直接将按技能树学习的费用也作为一个依赖,就无需考虑这个,这就是第三条建边规则。
按这么想的话,第一条和第二条也很好理解。
而当我所要学得那个技能的依赖全部消除的时候,那么源点与汇点也就会被分离,也就是被个开了,因为汇点只会与所要求的技能相连。

感觉还是有点说不好啊,如果还不懂的话,只要在纸上画一画,就会变得很显然了。

AC Code

#include 

using namespace std;

const int maxn = 2e3 + 5;
const int maxm = 2e4 + 5;
const int inf = 0x3f3f3f3f;

int n, m, src, des, idx;
int cur[maxn], level[maxn], head[maxn];

struct node {
    int to, next;
    int cap;
    node() {}
    node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm  que;

void addEdge(int u, int v, int c)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], 0); //无向图为 c 有向图为 0
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que.push(src);
    level[src] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].next) {
            int v = edges[id].to;
            if (edges[id].cap &gt; 0 &amp;&amp; level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[des] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == des)
        return low;
    for (int&amp; id = cur[u]; ~id; id = edges[id].next) {
        int v = edges[id].to;
        if (edges[id].cap &gt; 0 &amp;&amp; level[v] == level[u] + 1
            &amp;&amp; (cflow = dfs(v, min(low, edges[id].cap)))) {
            edges[id].cap -= cflow;
            edges[id ^ 1].cap += cflow;
            return cflow;
        }
    }
    return 0;
}


int dinic() { int ans = 0, cflow; while (bfs()) { for (int i = 0; i <= 2 * n + 2; i++) cur[i] = head[i]; while ((cflow = dfs(src, inf))) ans += cflow; } return ans; } void init(int s, int d) { memset(head, -1, sizeof head); idx = 0; src = s, des = d; } inline int in(int x) { return x << 1; } inline int out(int x) { return x << 1 | 1; } int main() { int T, u, v, w, t; scanf("%d", &T); while (T--) { scanf("%d %d %d", &n, &m, &t); init(0, 1); while (m--) { scanf("%d %d %d", &u, &v, &w); addEdge(out(u), in(v), w); } for (int i = 1; i <= n; i++) { scanf("%d", &w); addEdge(src, in(i), w); } for (int i = 1; i <= n; i++) { scanf("%d", &w); addEdge(in(i), out(i), w); } addEdge(out(t), des, inf); printf("%d\n", dinic()); } return 0; }

…………不知道为什么不把代码分开就显示不出来……

最小割

HDU 6126 Give out candies

Posted on

Table of contents

例行废话

哇~,惊了,多校里面第一次出现网络流的题目。然而我并没有时间甚至没有看它一眼……

我学了这么久的图论究竟是为了什么呢……
老实说我有一种不详的预感

现在想想的确是这样的,自己努力钻研的高级算法,又有多少会在比赛中用到呢……

回归正题

这是一道最小割+差分约束的题目,还是第一次遇到这两个结合起来。不过其实也只是分开来的问题,用差分约束判断可行性,再用最小割求解。

题意:
你要给\( n\) 个小朋友糖果,最少\( 1\)个,最多\( m \)个,并且你手上有无穷多的糖。并不是说给一个小朋友的糖果越多越好,给每一个小朋友不同糖果数量对应的愉悦值不同。我们自然希望小朋友的愉悦值最大化。
但这些小朋友也提出了一些要求,对于每一个要求\( ( x , y , z ) \),你给 \( x\) 的糖果数量 \( ax \) 与给\( y\) 的糖果数量\( ay\) 满足如下不等式 \( ax - ay \leq z \)。
问满足所有要求的最大愉悦值。
若无法满足,输出-1。

思路:

关于满足小朋友们的要求
这是整个问题的一个子问题,每个要求都是一个不等式,我们很自然地能够想到用差分约束去判断可行性。这个子问题是个差分约束的裸问题,这里不再赘述。

关于最小割建图
先直接上建图方式,下面有解释。
设源点\( S \) ,汇点\( T\) ,\( ( a , b ) \)表示给小朋友\( a\) 糖果 \( b \) 颗。
\( a \rightarrow b == c \) 表示 \( a\) 与 \( b\) 建边,容量为 \( c \)。

  • 对于每一个小朋友 \( p\) \( S \rightarrow ( p, 1 ) == inf , ( p , m ) \rightarrow T ==inf \)
  • 对于每一个小朋友 \( p\) 的每一个给定糖果数量 \( k\) 所得的愉悦值 \( w\) ,\( ( p, k ) \rightarrow ( p , k+1 ) \),注意后面不能越界。
  • 对于每一个限制要求 \( ax - ay \leq z \),再对于范围内的糖果数量 \( i\) ,建边\( ( x , i + z ) \rightarrow ( y , i ) == inf \)

因为给每个小朋友的糖果数量 \( w \leq 1000 \) 。( 题面上并没有说明,但是题解上说了…… )
那么我们可以这么想,我先给每个小朋友 1000 个糖果,然后再从小朋友中拿回一些糖果,我们要求最大值,自然是使得拿回的糖果造成的愉悦值减少最小,对于一个小朋友来说这就是一条割边。因为每个小朋友都要拿回糖果,所以对于整张图来说就是最小割了。

再是对每一个限制要求:写个题解好累,能自己理解去么……
对于\( (x , i + z ) \rightarrow ( y , i ) \) 可以这样想,如果我割掉了 \( ( x, i + z - 1 ) \rightarrow ( x , i + z ) \) ,那么如果你在 \( y\)不选择\( ( y, i ) \) 之后的边,那么上面那个割边就变的没有意义,从而你必须去割掉一条 \( inf\) 的边。
哎呀,自己在纸上画画就很清楚了……

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef pair<int, int> pii;
const int maxv = 55;
const int maxn = maxv * maxv;
const int maxm = maxn * maxn;
const int inf = 0x3f3f3f3f;

int n, m, k, st, en, idx;
int cur[maxn], level[maxn], head[maxn];
int kvis[maxv];

int mat[maxv][maxv];
int ku[155], kv[155], kw[155];

vector<pii> G[55];

struct node {
    int to, next;
    int cap;
    node() {}
    node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm << 1];

queue<int> que;
stack<int> stk;

inline int getNode(int a, int b) { return a * m + b; }

void addEdge(int u, int v, int c, int rc = 0)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], rc);
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que.push(st);
    level[st] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].next) {
            int v = edges[id].to;
            if (edges[id].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].next) {
        int v = edges[id].to;
        if (edges[id].cap > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].cap)))) {
            edges[id].cap -= cflow;
            edges[id ^ 1].cap += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= en; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

void Ginit()
{
    memset(kvis, false, sizeof kvis);
    for (int i = 0; i < n; i++)
        G[i].clear();
}

void init(int s, int e)
{
    st = s, en = e;
    memset(head, -1, sizeof head);
    idx = 0;
}

bool spfa(int st)
{
    bool vis[maxv];
    int dis[maxv], cnt[maxv];
    for (int i = 0; i <= n; i++) {
        cnt[i] = vis[i] = false;
        dis[i] = inf;
    }
    while (!stk.empty())
        stk.pop();
    dis[st] = 0, kvis[st] = vis[st] = true, cnt[st] = 1;
    stk.push(st);
    while (!stk.empty()) {
        int u = stk.top(), sz = G[u].size();
        stk.pop();
        vis[u] = false;
        for (int i = 0; i < sz; i++) {
            int v = G[u][i].first;
            if (dis[v] > dis[u] + G[u][i].second) {
                dis[v] = dis[u] + G[u][i].second;
                if (!vis[v]) {
                    kvis[v] = vis[v] = true;
                    stk.push(v);
                    if (++cnt[v] > n)
                        return false;
                }
            }
        }
    }
    return true;
}

void CreateGragh()
{
    m++;
    init(n * m, n * m + 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m - 1; j++)
            addEdge(getNode(i, j), getNode(i, j + 1), 1000 - mat[i][j]);
        addEdge(st, getNode(i, 0), inf);
        addEdge(getNode(i, m - 1), en, inf);
    }
    for (int p = 0; p < k; p++) {
        for (int i = 0; i + kw[p] < m; i++)
            addEdge(getNode(ku[p], i + kw[p]), getNode(kv[p], i), inf);
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d %d", &n, &m, &k);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                scanf("%d", &mat[i][j]);
        Ginit();
        for (int i = 0; i < k; i++) {
            scanf("%d %d %d", ku + i, kv + i, kw + i);
            ku[i]--, kv[i]--;
            G[ku[i]].push_back(make_pair(kv[i], kw[i]));
        }
        bool flag = false;
        for (int i = 0; i < n && !flag; i++)
            if (!kvis[i])
                if (!spfa(i)) {
                    flag = true;
                    break;
                }
        if (flag) {
            puts("-1");
            continue;
        }
        CreateGragh();
        int key = dinic();
        printf("%d\n", 1000 * n - key);
    }
    return 0;
}
最小割

ZOJ 3475 The Great Wall I

Posted on

最小割建图好题!!

昨天比赛的最小割,当时没看出来,实际上需要建图转化一下,这道题非常显然!!!
比赛后不想看题解,问了一下Yasola,指点了一下马上懂了!!

题意:
有n×m的地图,地图上最多有6个国家,现在K国要修长城,来防御敌对国家,6个国家中除了K国和一个敌对国家,其余国家都是友好国家,想要进供从而使得自己在长城防御范围内。建立长城的每一个花费都已经给出。
问最小花费。

思路:
将地图以外的地方视为敌对,将一个地图上的格子与其上下左右相连。
对于一个长城,实际上就是将K过与友好国家 与 敌对国家割开的最小割。
又因为点数和边数都很少,最多通过枚举 2^5 枚举将友好国家包围的情况,每次求一下最小割即可。

AC Code

#include <bits/stdc++.h>

using namespace std;
const int maxn = 404;
const int maxm = 1e4 + 5;
const int inf = 0x3f3f3f3f;

int n, m, st, en, idx, tidx;
int cur[maxn], level[maxn], head[maxn], thead[maxn];
int cap[maxm];
int afford[10], x[10], y[10];

struct node {
    int to, next;
    int cap;
    node() {}
    node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm << 1];

queue<int> que;

int getNode(int a, int b) { return a * m + b; }

void addEdge(int u, int v, int c)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], c);
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que.push(st);
    level[st] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].next) {
            int v = edges[id].to;
            if (edges[id].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].next) {
        int v = edges[id].to;
        if (edges[id].cap > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].cap)))) {
            edges[id].cap -= cflow;
            edges[id ^ 1].cap += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= en; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

int main()
{
    int c;
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(head, -1, sizeof head), idx = 0;
        st = n * m, en = n * m + 1;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &c);
                addEdge(i == 0 ? en : getNode(i - 1, j), i == n ? en : getNode(i, j), c);
            }
            if (i == n)
                continue;
            for (int j = 0; j <= m; j++) {
                scanf("%d", &c);
                addEdge(j == 0 ? en : getNode(i, j - 1), j == m ? en : getNode(i, j), c);
            }
        }
        scanf("%d", &c);
        for (int i = 0; i < c; i++) {
            scanf("%d %d %d", afford + i, x + i, y + i);
            if (afford[i] == 0)
                swap(afford[0], afford[i]), swap(x[0], x[i]), swap(y[0], y[i]);
            else if (afford[i] < 0)
                addEdge(getNode(x[i], y[i]), en, inf), c--, i--;
        }
        memcpy(thead, head, sizeof head), tidx = idx;
        for (int i = 0; i < idx; i++)
            cap[i] = edges[i].cap;
        int ans = inf;
        for (int i = 1; i < (1 << c); i += 2) {
            int cost = 0;
            memcpy(head, thead, sizeof thead), idx = tidx;
            for (int i = 0; i < idx; i++)
                edges[i].cap = cap[i];
            for (int j = 0; j < c; j++) {
                if (i & (1 << j)) {
                    cost -= afford[j];
                    addEdge(st, getNode(x[j], y[j]), inf);
                }
            }
            cost += dinic();
            ans = min(ans, cost);
        }
        printf("%d\n", ans);
    }
    return 0;
}
最小割

HDU 1565 1569 方格取数

Posted on

两道方格取数,第一道数据较小,可用状压dp求解,但是第二道数据增大1.5倍,状压就吃力了。
其实这里可以转化成最小割求解。

题意:
给你一个矩阵,矩阵中的每个数都有一定权值,当你取出其中一个数,与他上下左右相邻的数就不能被取。问你能取出的最大权值。

思路:
首先熟悉dp的人马上会想到。这是在一维相邻元素取舍的二位拓展。dp的思路易得。
但本人并不熟悉dp,只知道可写……
这里说的最小割解法。

先补一下所需前置知识。

  • 二分图点权最大独立集:带点权二分图G中的一个子集V,其中一条边的两个端点不能同时属于V,且V中点权和最大。
  • 点覆盖集:无向图G的一个点集,使得该图中所以边都至少有一个端点在该集合内。形式化的定时意思点覆盖集为V'∈V,满足对于所有的(u,v)∈E,都有u属于V'或v属于V'成立,即至少一个成立。形象的说是若干点“覆盖”住了与他们邻接的边。这些边恰好组成了原边集。
  • 最小点覆盖集: 在无向图G中,点数最小的覆盖集。
  • 最小点权覆盖集:在带点权无向图G中,点权之和最小的点覆盖集。

那么显然,点覆盖集的补集就是独立集,因为点覆盖集中每个边都至少被一个点覆盖,补集就不可能存在一条边的两个端点。
由此可得:二分图点权最大独立集=二分图点权和-二分图最小点权覆盖集

而二分图最小点权覆盖集可由最小割求得。

AC Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 3000;
const int inf = 0x3f3f3f3f;

int n, m, st, en, idx;
int level[maxn], cur[maxn];
int head[maxn];
int mat[60][60];
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };

struct node {
    int to;
    int nxt;
    int flow;
} edges[20010];

queue<int> que;

inline void addEdge(int u, int v, int flow)
{
    edges[idx].to = v;
    edges[idx].flow = flow;
    edges[idx].nxt = head[u];
    head[u] = idx++;

    edges[idx].to = u;
    edges[idx].flow = 0;
    edges[idx].nxt = head[v];
    head[v] = idx++;
}

bool bfs()
{
    while (!que.empty())
        que.pop();
    memset(level, -1, sizeof level);
    que.push(st);
    level[st] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            int v = edges[id].to;
            if (edges[id].flow && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].nxt) {
        int v = edges[id].to;
        if (edges[id].flow && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].flow)))) {
            edges[id].flow -= cflow;
            edges[id ^ 1].flow += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = st; i <= en; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

void init(int s, int e)
{
    st = s, en = e;
    memset(head, -1, sizeof head);
    idx = 0;
}

int main()
{
    int x, y;
    while (scanf("%d %d", &n, &m) != EOF) {
        int sum = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                scanf("%d", &mat[i][j]);
                sum += mat[i][j];
            }
        init(0, n * m + 1);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (((i + j) & 1) == 0) {
                    addEdge(st, (i - 1) * m + j, mat[i][j]);
                    for (int k = 0; k < 4; k++) {
                        x = i + dx[k];
                        y = j + dy[k];
                        if (x < 1 || x > n || y < 1 || y > m)
                            continue;
                        addEdge((i - 1) * m + j, (x - 1) * m + y, inf);
                    }
                } else
                    addEdge((i - 1) * m + j, en, mat[i][j]);
        printf("%d\n", sum - dinic());
    }
    return 0;
}