P2774 方格取数问题

不相邻取数是带权二分图独立集

问题

P2774 方格取数问题
给定一个 $m\times n$ 的正权方格，可以选择若干格，但任意两个被选格子不能共边。要求选择格子的权值和最大。

数据规模：$1\le m,n\le100$，$1\le a_{i,j}\le10^5$。

把每个格子看成一个顶点，两个共边格子之间连接一条冲突边。

题目要求选择若干顶点，并保证任意一条冲突边的两个端点不能同时被选择，这正是 独立集 的定义。由于每个格子还有权值，所以题目要求的是最大权独立集。

而如果按照棋盘给格子黑白染色，会发现冲突边都恰好连接了黑白两种颜色，所以整张冲突图天然就是一张二分图。

最小割模型不擅长解决 “哪些点可以同时保留”，它更适合表达 “为了消除冲突需要支付哪些点的代价”，于是我们转向 “独立集” 模型的补集 “点覆盖” 模型。

独立集与点覆盖

如果一个点不在独立集中，就把它放入被删除的集合。因为独立集中不能同时出现一条边的两个端点，所以对于原图中的任意一条边，至少有一个端点必须被删除。也就是说，独立集的补集一定覆盖原图中的每一条边，这正是点覆盖。

反过来，若一个集合是点覆盖，那么删除这些点以后不再存在完整的边，因此剩余顶点构成独立集。

而由于所有点的权值总和固定，因此有：最大权独立集 = 全部点权和 - 最小权点覆盖。

注：此处的补集关系不依赖于二分图，二分图的关键在于可以使用最小割来求解最小权点覆盖。

于是我们可以把黑点放在左部，白点放在右部，如下建立：

• $S\to$ 黑点，容量为黑点权值；
• 白点 $\to T$，容量为白点权值；
• 每条黑白冲突边连接黑点 $\to$ 白点，容量为 inf。

如果一个黑点被放到汇侧，那么 $S\to$ 黑点会被割，支付这个黑点的权值。可以把它解释为：选择这个黑点加入点覆盖。

反之如果一个白点被放到源侧，那么白点 $\to T$ 会被割，同样支付这个白点的权值：选择这个白点加入点覆盖。

所以割容量就是被选入点覆盖的所有顶点权值之和。

正无穷的边为什么能保证覆盖所有冲突呢？

考虑一条冲突边 $u\to v$，其中 $u$ 是黑点，$v$ 是白点。

如果黑点 $u$ 留在源侧，说明没有支付 $u$ 的权值，它没有进入点覆盖；如果白点 $v$ 留在汇侧，同样没有支付 $v$ 的权值。也就是说，这种状态表示这条冲突边的两个端点都没有被点覆盖选择。

此时 inf 边 $u\to v$ 恰好会跨割，因此任何有限最优割都不会允许这种情况发生。所以每条冲突边至少有一个端点会被支付权值，也就是至少选择一个端点进入点覆盖。

于是：最小割 = 最小权点覆盖。最终答案就是：权值总和 - 最小割，也就是最大权独立集。

▶

P2774 建图

namespace DINIC { /* 模板代码略 */ }
using namespace DINIC;

ll a[105][105];
int m, n;

int encode( int x, int y ) {
    return ( x - 1 ) * n + y;
}

int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };

void solve( ) {
    m = read( ), n = read( );
    
    int S = 0, T = m * n + 1;
    init( T );

    ll sum = 0;

    for( int i = 1; i <= m; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            a[i][j] = read( );
            sum += a[i][j];
            int id = encode( i, j );
            if( ( i + j ) & 1 ) add_edge( S, id, a[i][j] );
            else add_edge( id, T, a[i][j] );
        }
    }

    for( int i = 1; i <= m; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            if( ( ( i + j ) & 1 ) == 0 ) continue;
            int id = encode( i, j );
            for( int dir = 0; dir < 4; ++ dir ) {
                int nx = i + dx[dir];
                int ny = j + dy[dir];
                if( nx < 1 || nx > m || ny < 1 || ny > n ) continue;
                int nid = encode( nx, ny );
                add_edge( id, nid, inf );
            }
        }
    }

    ll mncut = Dinic( S, T, T );
    cout << sum - mncut << '\n';
}