BZOJ板刷计划(1/300) BZOJ1001 狼抓兔子

狼抓颓子

最小割最大流模板。

堵掉一条边的代价是边权，使ST不连通，显然是最小割问题。

以左上为源点，右下为汇点，建立流网络，边的容量是边权（注意，因为每条边是双向的，所以反向边容量设置成与正向边一样），然后跑最大流即可。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using int_t = int;

using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 2000000;
const int_t INF = 0x3ffffff;
struct Edge
{
    int_t from;
    int_t to;
    int_t flow = 0;
    int_t capacity;
    Edge(int_t from, int_t to, int_t capacity)
    {
        this->from = from;
        this->to = to;
        this->capacity = capacity;
    }
}__attribute__((aligned(1)));

std::vector<Edge> edges;
std::vector<int_t> graph[LARGE + 1];

void pushEdge(int_t from, int_t to, int_t capacity)
{
    edges.push_back(Edge(from, to, capacity));
    edges.push_back(Edge(to, from, capacity));
    graph[from].push_back(edges.size() - 2);
    graph[to].push_back(edges.size() - 1);
    // cout << "pushing edge " << from << " " << to << " " << capacity << endl;
}

namespace maxflow
{
int_t vertex_n;
int_t dis[LARGE + 1];
int_t curr[LARGE + 1];
bool visited[LARGE + 1];
bool BFS(int_t source, int_t sink)
{
    std::fill(curr + 1, curr + 1 + vertex_n, 0);
    std::fill(dis + 1, dis + 1 + vertex_n, 0x7fffffff);
    std::fill(visited + 1, visited + 1 + vertex_n, false);

    std::queue<int_t> queue;
    dis[source] = 0;
    queue.push(source);
    visited[source] = true;
    while (queue.empty() == false)
    {
        auto front = queue.front();
        queue.pop();

        for (auto id : graph[front])
        {
            auto &edge = edges[id];
            if (edge.capacity > edge.flow && visited[edge.to] == false)
            {
                dis[edge.to] = dis[front] + 1;
                queue.push(edge.to);
                visited[edge.to] = true;
            }
        }
    }
    return visited[sink];
}
int_t DFS(int_t vertex, int_t sink, int_t minf = INF)
{
    if (vertex == sink || minf == 0)
        return minf;
    int_t result = 0;
    for (int_t &i = curr[vertex]; i < graph[vertex].size(); i++)
    {
        auto id = graph[vertex][i];
        auto &edge = edges[id];
        if (dis[edge.to] == dis[vertex] + 1)
        {
            int_t x = DFS(edge.to, sink, std::min(minf, edge.capacity - edge.flow));
            if (x > 0)
            {
                // cout << "at vertex " << vertex << " flow " << x<<" to vertex "<<edge.to << endl;
                result += x;
                minf -= x;
                edges[id].flow += x;
                edges[id ^ 1].flow -= x;
            }
            if (minf == 0)
                break;
        }
    }
    return result;
}

int_t execute(int_t source, int_t sink)
{
    int_t result = 0;
    while (BFS(source, sink))
    {
        int_t temp = DFS(source, sink);
        // cout << temp << endl;
        // if (temp == 0)
        //     break;
        result += temp;
    }
    return result;
}
} // namespace maxflow
int_t encode(int_t r, int_t c, int_t n, int_t m)
{
    return (r - 1) * m + c;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int_t i = 1; i <= n; i++)
    {
        for (int_t j = 1; j < m; j++)
        {
            int capacity;
            scanf("%d", &capacity);
            pushEdge(encode(i, j, n, m), encode(i, j + 1, n, m), capacity);
        }
    }
    for (int_t i = 1; i < n; i++)
    {
        for (int_t j = 1; j <= m; j++)
        {
            int capacity;
            scanf("%d", &capacity);
            pushEdge(encode(i, j, n, m), encode(i + 1, j, n, m), capacity);
        }
    }
    for (int_t i = 1; i < n; i++)
    {
        for (int_t j = 1; j < m; j++)
        {
            int capacity;
            scanf("%d", &capacity);
            pushEdge(encode(i, j, n, m), encode(i + 1, j + 1, n, m), capacity);
        }
    }
    maxflow::vertex_n = n * m * 2;
    printf("%d", maxflow::execute(encode(1, 1, n, m), encode(n, m, n, m)));
    return 0;
}