题目大意
解题报告
2018/4/12 Update: 发现以前的题解不负责任地出错了..已修正。
此题bzoj的Discuss上有很多好的测试数据,我就不给啦!
怎么感觉这题和Ex咖喱棒没任何关系啊。。
首先发现如果取了一个格子那么格子四周的格子都不能取,
因为格子内的数大于0,那么题目就变成了:
求N*M矩阵内取格子内的数字,使得数字和最大且格子两两不相邻。
接下来就是套路了。。
发现把每个格子的(i,j)按照i+j的奇偶性分成黑白两类,(就是按照网格状二染色),那么黑色选了,相邻的白色就不能选。
这是一个二分图, 所以可以做到用二染色和连接INF边满足相邻两个节点不能同时被选择的约束。
那么把黑色点和S(源点)连边,权值为格子上的数字。把白色点和T(汇点点)连边,权值也为格子上的数字,每个白点向相邻的黑点连INF的边。
现在考虑最小割把所有点分为两部分。
对于白点, s集(源点所在集合)中的点代表不被选中,t集(汇点所在集和)中的点被选中, 对于黑点则恰好相反。
答案就等于总权值和减去最小割啦~
下面上代码:
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
const int INF = 0x3f3f3f3f;
const int MAXN = 100+10;
using std :: min;
using std :: max;
namespace isap {
const int MAXD = 10000;
const int MAXE = 1000000;
struct Node {
int v, w, bk, nxt;
} d[MAXE];
int head[MAXD], etot;
inline int addEdge (int a, int b, int c) {
etot ++;
d[etot].v = b;
d[etot].w = c;
d[etot].bk = etot + 1;
d[etot].nxt = head[a];
head[a] = etot;
etot ++;
d[etot].v = a;
d[etot].w = 0;
d[etot].bk = etot - 1;
d[etot].nxt = head[b];
head[b] = etot;
//printf("%d -> %d: %d\n", a, b, c);
return etot;
}
int dis[MAXD], vd[MAXD];
int seq[MAXD+100];
void bfs (int s) {
int lef, rig;
memset(dis, 0x3f, sizeof dis);
dis[seq[lef = rig = 0] = s] = 0;
while(lef <= rig) {
int u = seq[lef++];
for(int e = head[u]; e; e = d[e].nxt)
if(dis[d[e].v] > dis[u] + 1) {
dis[d[e].v] = dis[u] + 1;
seq[++rig] = d[e].v;
}
}
}
int S, T, N;
int dfs (int u, int val) {
//printf("at:%d, val:%d\n", u, val);
if(u == T) return val;
int rest = val;
for(int e = head[u]; e; e = d[e].nxt)
if(d[e].w && dis[d[e].v]+1 == dis[u]) {
int t = dfs(d[e].v, min(rest, d[e].w));
rest -= t;
d[e].w -= t;
d[d[e].bk].w += t;
if(!rest) return val;
if(dis[S] >= N) return val - rest;
}
if(val == rest) {
if(!(--vd[dis[u]])) {dis[S] = N; return 0;}
dis[u] = N;
for(int e = head[u]; e; e = d[e].nxt)
if(d[e].w) dis[u] = min(dis[u], dis[d[e].v] + 1);
++ vd[dis[u]];
return 0;
}
return val - rest;
}
int sap (int s, int t, int n) {
S = s, T = t, N = n;
bfs(T);
for(int i = 1; i<=N; i++)
if(dis[i] <= N) vd[dis[i]] ++;
int flow = 0;
while(dis[S] < N) flow += dfs(S, INF);
return flow;
}
void clear() {
etot = 0;
memset(head, 0, sizeof head);
}
}
int N, M;
int val[MAXN][MAXN];
int getVid (int x, int y) {
return (x-1)*M+y;
}
int main () {
int sum = 0;
scanf("%d%d", &N, &M);
int S = 1, T = S+N*M+1;
for(int i = 1; i<=N; i++)
for(int j = 1; j<=M; j++) {
scanf("%d", &val[i][j]), sum += val[i][j];
if((i+j)&1) isap :: addEdge(S, S+getVid(i, j), val[i][j]);
else isap :: addEdge(S+getVid(i, j), T, val[i][j]);
}
for(int i = 1; i<=N; i++)
for(int j = 1; j<=M; j++)
if((i+j)&1) {
int id = getVid(i, j);
if(i != 1) isap :: addEdge(S+id, S+getVid(i-1, j), INF);
if(i != N) isap :: addEdge(S+id, S+getVid(i+1, j), INF);
if(j != 1) isap :: addEdge(S+id, S+getVid(i, j-1), INF);
if(j != M) isap :: addEdge(S+id, S+getVid(i, j+1), INF);
}
printf("%d\n", sum - isap :: sap(S, T, T));
}
Join the discussion