#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define N 3000 #define M 10000 #define inf 1073741824 #define ll int //N为点数 M为边数 struct Edge{ int from, to, cap, nex; }edge[M*10];//注意这个一定要够大 不然会re 还有反向弧 int head[N], edgenum; void addedge(int u, int v, ll cap){ Edge E = { u, v, cap, head[u]}; edge[ edgenum ] = E; head[u] = edgenum ++; Edge E2= { v, u, 0, head[v]}; edge[ edgenum ] = E2; head[v] = edgenum ++; } int sign[N], s, t; bool BFS(int from, int to){ memset(sign, -1, sizeof(sign)); sign[from] = 0; queue q; q.push(from); while( !q.empty() ){ int u = q.front(); q.pop(); for(int i = head[u]; i!=-1; i = edge[i].nex) { int v = edge[i].to; if(sign[v]==-1 && edge[i].cap) { sign[v] = sign[u] + 1, q.push(v); if(sign[to] != -1)return true; } } } return false; } int Stack[M*4], top, cur[M*4]; ll dinic(){ ll ans = 0; while( BFS(s, t) ) { memcpy(cur, head, sizeof(head)); int u = s; top = 0; while(1) { if(u == t) { ll flow = inf;int loc;//loc 表示 Stack 中 cap 最小的边 for(int i = 0; i < top; i++) if(flow > edge[ Stack[i] ].cap) { flow = edge[Stack[i]].cap; loc = i; } for(int i = 0; i < top; i++) { edge[ Stack[i] ].cap -= flow; edge[Stack[i]^1].cap += flow; } ans += flow; top = loc; u = edge[Stack[top]].from; } for(int i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增广的边的下标 if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break; if(cur[u] != -1) { Stack[top++] = cur[u]; u = edge[ cur[u] ].to; } else { if( top == 0 )break; sign[u] = -1; u = edge[ Stack[--top] ].from; } } } return ans; } int n, m; int idx(int x, int y){return x*m+y;} int main(){ int i, j; while(~scanf("%d%d",&n,&m)){ memset(head, -1, sizeof(head)), edgenum = 0; s = n*m+1; t = s+1; ll sum = 0, now; for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) { scanf("%d",&now); sum+=now; int num = (i-1)*m+j; if((i+j)&1) { addedge(s, num, now); if(i>1) addedge(num, num-m, inf); if(i 1) addedge(num, num-1, inf); if(j