两道方格取数,第一道数据较小,可用状压dp求解,但是第二道数据增大1.5倍,状压就吃力了。
其实这里可以转化成最小割求解。

题意:
给你一个矩阵,矩阵中的每个数都有一定权值,当你取出其中一个数,与他上下左右相邻的数就不能被取。问你能取出的最大权值。

思路:
首先熟悉dp的人马上会想到。这是在一维相邻元素取舍的二位拓展。dp的思路易得。
但本人并不熟悉dp,只知道可写……
这里说的最小割解法。

先补一下所需前置知识。

  • 二分图点权最大独立集:带点权二分图G中的一个子集V,其中一条边的两个端点不能同时属于V,且V中点权和最大。
  • 点覆盖集:无向图G的一个点集,使得该图中所以边都至少有一个端点在该集合内。形式化的定时意思点覆盖集为V'∈V,满足对于所有的(u,v)∈E,都有u属于V'或v属于V'成立,即至少一个成立。形象的说是若干点“覆盖”住了与他们邻接的边。这些边恰好组成了原边集。
  • 最小点覆盖集: 在无向图G中,点数最小的覆盖集。
  • 最小点权覆盖集:在带点权无向图G中,点权之和最小的点覆盖集。

那么显然,点覆盖集的补集就是独立集,因为点覆盖集中每个边都至少被一个点覆盖,补集就不可能存在一条边的两个端点。
由此可得:二分图点权最大独立集=二分图点权和-二分图最小点权覆盖集

而二分图最小点权覆盖集可由最小割求得。

AC Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 3000;
const int inf = 0x3f3f3f3f;

int n, m, st, en, idx;
int level[maxn], cur[maxn];
int head[maxn];
int mat[60][60];
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };

struct node {
    int to;
    int nxt;
    int flow;
} edges[20010];

queue<int> que;

inline void addEdge(int u, int v, int flow)
{
    edges[idx].to = v;
    edges[idx].flow = flow;
    edges[idx].nxt = head[u];
    head[u] = idx++;

    edges[idx].to = u;
    edges[idx].flow = 0;
    edges[idx].nxt = head[v];
    head[v] = idx++;
}

bool bfs()
{
    while (!que.empty())
        que.pop();
    memset(level, -1, sizeof level);
    que.push(st);
    level[st] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].nxt) {
            int v = edges[id].to;
            if (edges[id].flow && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].nxt) {
        int v = edges[id].to;
        if (edges[id].flow && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].flow)))) {
            edges[id].flow -= cflow;
            edges[id ^ 1].flow += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = st; i <= en; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

void init(int s, int e)
{
    st = s, en = e;
    memset(head, -1, sizeof head);
    idx = 0;
}

int main()
{
    int x, y;
    while (scanf("%d %d", &n, &m) != EOF) {
        int sum = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                scanf("%d", &mat[i][j]);
                sum += mat[i][j];
            }
        init(0, n * m + 1);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (((i + j) & 1) == 0) {
                    addEdge(st, (i - 1) * m + j, mat[i][j]);
                    for (int k = 0; k < 4; k++) {
                        x = i + dx[k];
                        y = j + dy[k];
                        if (x < 1 || x > n || y < 1 || y > m)
                            continue;
                        addEdge((i - 1) * m + j, (x - 1) * m + y, inf);
                    }
                } else
                    addEdge((i - 1) * m + j, en, mat[i][j]);
        printf("%d\n", sum - dinic());
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Related Posts

最小割

51Nod 1499 图

emmmmmmm不错的的最小割吧 唯一一个不是很好的点就是实在是太容易 Read more…

最小割

HihoCoder 1252 Kejin Game

网络流建图神题!!! 同时也是2015年北京现场赛的金牌题,虽然我不可 Read more…

最小割

HDU 6126 Give out candies

例行废话 哇~,惊了,多校里面第一次出现网络流的题目。然而我并没有时间 Read more…