Description
给定一个 \(n~\times~m\) 的矩阵，每个位置有一个正整数，选择一些互不相邻的数，最大化权值和
Limitation
\(1~\leq~n,~m~\leq~100\)
Solution
由于数必须互不相邻，考虑二分图。
将矩阵染成二分图，相邻的格子连边，这样一条边的两个端点不能被同时选择，问题就被转化为了二分图上的最大带权独立集问题。
有关二分图的几个定理：
二分图最小无权点覆盖 = 二分图最大匹配
二分图最小无权边覆盖 = 总点数 - 二分图最大匹配
二分图最大无权独立集 = 总点数 - 二分图最大匹配
如果点带点 正 权，则源点向左部连边，容量为点权，右部向汇点连边，容量为点权，原边保留，容量无穷。
二分图最小权点覆盖 = 最小割
二分图最大权独立集 = 点权和 - 最小割
最小点权覆盖的证明与最大权闭合子图的证明类似，证明在，最大权独立集的证明需要 最大独立集 = 全集 - 最小点覆盖 的引理。
于是这题跑一个最小割就可以解决了。
Code
#include#include #include #include #ifdef ONLINE_JUDGE#define freopen(a, b, c)#endiftypedef long long int ll;namespace IPT { const int L = 1000000; char buf[L], *front=buf, *end=buf; char GetChar() { if (front == end) { end = buf + fread(front = buf, 1, L, stdin); if (front == end) return -1; } return *(front++); }}template inline void qr(T &x) { char ch = IPT::GetChar(), lst = ' '; while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar(); while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar(); if (lst == '-') x = -x;}namespace OPT { char buf[120];}template inline void qw(T x, const char aft, const bool pt) { if (x < 0) {x = -x, putchar('-');} int top=0; do {OPT::buf[++top] = static_cast (x % 10 + '0');} while (x /= 10); while (top) putchar(OPT::buf[top--]); if (pt) putchar(aft);}const int maxn = 10010;const int maxm = 105;const int INF = 100000000;struct Edge { int u, v, flow; Edge *nxt, *bk; Edge(const int _u, const int _v, const int _flow, Edge* &h) { this->u = _u; this->v = _v; this->flow = _flow; this->nxt = h; h = this; }};Edge *hd[maxn], *fir[maxn];inline void cont(const int _u, const int _v, const int _flow) { auto u = new Edge(_u, _v, _flow, hd[_u]), v = new Edge(_v, _u, 0, hd[_v]); (u->bk = v)->bk = u;}int n, m, s, t, ans;int MU[maxn], id[maxm][maxm], col[maxm][maxm], dist[maxn];std::queue Q;bool bfs();int dfs(const int u, int canag);void link(const int x, const int y);int main() { freopen("1.in", "r", stdin); qr(n); qr(m); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { qr(MU[id[i][j] = ++t]); ans += MU[t]; } s = ++t; ++t; for (int i = 1; i <= n; ++i) { if ((col[i][1] = col[i - 1][1] ^ 1)) link(i, 1); else cont(id[i][1], t, MU[id[i][1]]); for (int j = 2; j <= m; ++j) if ((col[i][j] = col[i][j - 1] ^ 1)) link(i, j); else cont(id[i][j], t, MU[id[i][j]]); } while (bfs()) { for (int i = 1; i <= t; ++i) fir[i] = hd[i]; ans -= dfs(s, INF); } qw(ans, '\n', true); return 0;}bool bfs() { memset(dist, 0, sizeof dist); Q.push(s); dist[s] = 1; while (!Q.empty()) { int u = Q.front(); Q.pop(); for (auto e = hd[u]; e; e = e->nxt) if (e->flow > 0) { int v = e->v; if (dist[v]) continue; dist[v] = dist[u] + 1; Q.push(v); } } return dist[t];}int dfs(const int u, int canag) { if ((u == t) || (!canag)) return canag; int _f = 0; for (auto &e = fir[u]; e; e = e->nxt) if (e->flow > 0) { int v = e->v; if (dist[v] != (dist[u] + 1)) continue; int f = dfs(v, std::min(canag, e->flow)); e->flow -= f; e->bk->flow += f; _f += f; if (!(canag -= f)) break; } return _f;}void link(const int x, const int y) { int u = id[x][y]; cont(s, u, MU[u]); if (x > 1) cont(u, id[x - 1][y], INF); if (y < m) cont(u, id[x][y + 1], INF); if (y > 1) cont(u, id[x][y - 1], INF); if (x < n) cont(u, id[x + 1][y], INF);}