Codeforces Gym101518H：No Smoking, Please（最小割）

题目链接

题意

给出一个n*m的酒店，每个点是一个房间，要将这个酒店的房间划分成为两块（一块无烟区，一块吸烟区），相邻的两个房间之间有一条带权边，权值代表空气锁的面积，如果把这条边给去掉，那么需要花费（空气锁的面积+开一个窗口传食物）*1000元。问需要的最少花费是多少。要注意如果面积为0，则这条边不能划分。

思路

全场做的人不多，主要看题意比较难，看懂题意就会发现是裸的最小割，但是有个面积为0的坑点。这里的边需要开的比较大，考虑到每次增加两个点，就会使边增加三条（不知道这样想对不对），于是就开两倍（还有两倍双向边）。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int M = 1e3 + 11;
const int N = 1e6 + 11;
struct Edge {
    int u, v, nxt, cap;
} edge[N*4];
int head[N], tot, id[M][M];
int cur[N], gap[N], dis[N], pre[N];
queue<int> que;

void Add(int u, int v, int cap) {
    edge[tot] = (Edge) { u, v, head[u], cap }; head[u] = tot++;
    edge[tot] = (Edge) { v, u, head[v], cap }; head[v] = tot++;
}

void BFS(int T) {
    while(!que.empty()) que.pop();
    memset(dis, INF, sizeof(dis));
    memset(gap, 0, sizeof(gap));
    gap[0] = 1; dis[T] = 0;
    que.push(T);
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = edge[i].nxt) {
            int v = edge[i].v;
            if(dis[v] != INF) continue;
            dis[v] = dis[u] + 1;
            gap[dis[v]]++;
            que.push(v);
        }
    }
}

int ISAP(int S, int T, int n) {
    BFS(T);
    memcpy(cur, head, sizeof(cur));
    int i, flow, u = pre[S] = S, index, ans = 0;
    while(dis[S] < n) {
        if(u == T) {
            flow = INF, index = u;
            for(u = S; u != T; u = edge[cur[u]].v)
                if(edge[cur[u]].cap < flow) flow = edge[cur[u]].cap, index = u;
            for(u = S; u != T; u = edge[cur[u]].v)
                edge[cur[u]].cap -= flow, edge[cur[u]^1].cap += flow;
            u = index, ans += flow;
        }
        for(i = cur[u]; ~i; i = edge[i].nxt)
            if(dis[edge[i].v] == dis[u] - 1 && edge[i].cap) break;
        if(~i) {
            pre[edge[i].v] = u; cur[u] = i; u = edge[i].v;
        } else {
            if(--gap[dis[u]] == 0) break;
            int md = n + 1;
            for(i = head[u]; ~i; i = edge[i].nxt)
                if(edge[i].cap && dis[edge[i].v] < md) md = dis[edge[i].v], cur[u] = i;
            gap[dis[u] = md + 1]++;
            u = pre[u];
        }
    } return ans;
}

int main() {
    int t; scanf("%d", &t);
    while(t--) {
        memset(head, -1, sizeof(head));
        tot = 0;
        int n, m, sx, sy, ex, ey;
        scanf("%d%d", &n, &m);
        scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
        int cnt = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) id[i][j] = ++cnt;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m - 1; j++) {
                int cap; scanf("%d", &cap);
                if(cap) Add(id[i][j], id[i][j+1], cap + 1);
            }
        }
        for(int i = 0; i < n - 1; i++) {
            for(int j = 0; j < m; j++) {
                int cap; scanf("%d", &cap);
                if(cap) Add(id[i][j], id[i+1][j], cap + 1);
            }
        }
        printf("%d
", ISAP(id[sx][sy], id[ex][ey], n * m) * 1000);
    } return 0;
}