【最小割】P1361 小M的作物

P1361 小M的作物

建图好题。

思路

看得出来还是经典的两者取一模型,也就是找出一种割边方式,将点划分为两个集合,且割边花费最小。但是给出的是收益而非费用,怎么办呢?

最大收益=总收益-最小损失。

总收益就是把题目给出的种A地种B地的收益以及组合的bonus全部加起来。最小损失就是跑最大流(=最小割)。

将种\(A\)地视为源点,种\(B\)地视为汇点。

下面考虑某一种作物的情况:

因为是假设从一开始就有总收益,也就是一种作物既种\(A\)地也种\(B\)地,之后再考虑放弃哪一边使种植方案可行,所以对于每一种作物\(i\),连边\(A→i\),\(i→B\)。

再考虑组合bonus:

只有当组合内所有作物都种在同一个地方才能得到bonus,那么可以尝试把整个组合视为一个点,但我们无法真正地用一个点代表一个组合(毕竟不像SCC缩点),所以考虑用两个新点(注意不能用组合内的点,且一定要两个点)\(x\)和\(y\)作为这个组合的代表,其中\(x\)代表组合种\(A\)地,\(y\)代表组合种\(B\)地。故连边\(A→x\)和\(y→B\)。而内部的所有点是无法切断的整体,故对于组合内的点\(corn[i]\),连边\(x→corn[i]\)和\(corn[i]→y\),边权均为\(INF\)。

然后跑最大流得出最小割,也就是最小损失,用总收益减去即得答案。

注意总顶点数是\(n+2+m*2\)(\(n\)种作物+源点汇点+每个组合两个代表点),虽然不知道为什么写成\(n+2\)也能过……

const int INF = 2005020600;
const int maxn = 6e4 + 100;
const int maxm = 2e6 + 100;

struct Edge {
    int from, to;
    LL w;
    int next;
}e[maxm];

int cnt_e = 0, head[maxn], n, m;
int s, t;
int cur[maxn], depth[maxn], gap[maxn];
int corn[maxn];
LL Maxflow = 0;

void addn(int u, int v, LL w) {
    //网络流建图
    e[++cnt_e].next = head[u]; e[cnt_e].from = u; e[cnt_e].to = v; e[cnt_e].w = w; head[u] = cnt_e;
    e[++cnt_e].next = head[v]; e[cnt_e].from = v; e[cnt_e].to = u; e[cnt_e].w = 0; head[v] = cnt_e;
}

void bfs() {
    mem(depth, -1);
    mem(gap, 0);
    depth[t] = 0;
    gap[0] = 1;
    cur[t] = head[t];
    queue<int> q;
    q.push(t);
    while (q.size()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;
            if (depth[v] != -1) continue;
            q.push(v);
            depth[v] = depth[u] + 1;
            gap[depth[v]]++;
        }
    }
    return;
}

LL dfs(int now, LL minflow,int n) {
    if (now == t) {
        Maxflow += minflow;
        return minflow;
    }
    LL nowflow = 0;
    for (int i = cur[now]; i; i = e[i].next) {
        cur[now] = i;
        int v = e[i].to;
        if (e[i].w && depth[v] + 1 == depth[now]) {
            LL k = dfs(v, min(e[i].w, minflow - nowflow), n);
            if (k) {
                e[i].w -= k;
                e[i ^ 1].w += k;
                nowflow += k;
            }
            if (minflow == nowflow) return nowflow;
        }
    }
    gap[depth[now]]--;
    if (!gap[depth[now]]) depth[s] = n + 1;
    depth[now]++;
    gap[depth[now]]++;
    return nowflow;
}

LL ISAP(int n) {
    Maxflow = 0;
    bfs();
    while (depth[s] < n) {
        memcpy(cur, head, sizeof(head));
        dfs(s, INF, n);
    }
    return Maxflow;
}

int main() {
    ios::sync_with_stdio(false);
    n = read();
    s = n + 1; t = n + 2;
    cnt_e = 1;
    int sum = 0;
    f(i, 1, n) {
        int x; x = read();
        addn(s, i, x);
        sum += x;
    }
    f(i, 1, n) {
        int x; x = read();
        addn(i, t, x);
        sum += x;
    }
    m = read();
    f(i, 1, m) {
        int k, c1, c2; k = read(); c1 = read(); c2 = read();
        sum += c1 + c2;
        //m个组合,每个组合k种作物
        f(j, 1, k) corn[j] = read();
        //给这个组合新建一个点,入边连源点,出边连组合内其他点
        //编号无所谓,不和已有的重复就行
        addn(s, n + 2 + i, c1);
        f(j, 1, k) addn(n+2+i, corn[j], INF);
        //给这个组合再新建一个点,入边连组合内其他点,出边连汇点
        addn(n + 2 + i + m, t, c2);
        f(j, 1, k) addn(corn[j], n + 2 + i + m, INF);
        //一个组合必须有不同的两个点分别连源点和汇点,否则冲突
    }
    int mincost = ISAP(n + 2 + m * 2);
    //跑最大流,求出的是最小割,也就是最小损失
    //答案求的是最大收益,总收益-最小损失即可
    printf("%d", sum - mincost);
    return 0;
}
上一篇:linux 查看目录容量


下一篇:理解二叉树递归中的自底向上和自顶向下两种思想