前言

前置知识 ：【网络流】最大流， 【网络流】最小割， 【网络流】最小点权覆盖集

宣传 ： 算法主页

问题描述

给定一张无向图 $G = (V, E)$ 。

求一个点集 $S\in V$ ，

使得所有 $u\in S$ 两两之间没有直接连边。

结论

$S’$ 为独立集 $S$ 的补集。

则一定满足： $S’$ 为原图的一个覆盖集。

证明

利用反证法。

若 $S’$ 不是一个覆盖集

则一定存在一条边 $(u, v)$

满足 $u\notin S’ 且 v\notin S’$

即 $u \in S 且 v\in S$

又因为 $S$ 是一个独立集，假设不成立

所以 $S’$ 是一个覆盖集

实现

#include <bits/stdc++.h>

using namespace std;

const int N = 10010, M = 60010, inf = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], c[M], ne[M], idx;
int q[N], dep[N], cur[N];

int get(int x, int y)
{
    return m * (x - 1) + y;
}

void add(int u, int v, int w)
{
    e[idx] = v, c[idx] = w, ne[idx] = h[u], h[u] = idx ++ ;
    e[idx] = u, c[idx] = 0, ne[idx] = h[v], h[v] = idx ++ ;
}

bool bfs()
{
    memset(dep, -1, sizeof dep);
    int hh = 0, tt = 0;
    q[0] = S, dep[S] = 0;
    cur[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dep[j] == -1 && c[i] > 0)
            {
                dep[j] = dep[t] + 1;
                cur[j] = h[j];
                if (j == T)return true;
                q[++ tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if (u == T)return limit;
    int flow = 0;
    for (int i = cur[u]; ~i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int j = e[i];
        if (dep[j] == dep[u] + 1 && c[i] > 0)
        {
            int t = find(j, min(c[i], limit - flow));
            if (!t)dep[j] = -1;
            c[i] -= t, c[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic()
{
    int res = 0, flow;
    while (bfs()) while (flow = find(S, inf))res += flow;
    return res;
}

int build()
{
    scanf("%d%d", &n, &m);
    S = 0, T = n * m + 1;
    memset(h, -1, sizeof h);
    int tot = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            int w;
            scanf("%d", &w);
            if (i + j & 1)
            {
                add(S, get(i, j), w);
                if (i > 1)add(get(i, j), get(i - 1, j), inf);
                if (i < n)add(get(i, j), get(i + 1, j), inf);
                if (j > 1)add(get(i, j), get(i, j - 1), inf);
                if (j < m)add(get(i, j), get(i, j + 1), inf);            
            }
            else add(get(i, j), T, w);
            tot += w;
        }
    return tot;
}

int main()
{
    printf("%d", build() - dinic());
    return 0;
}