[Medium] P8215 [THUPC 2022 初赛] 分组作业

简要题意

有 $2n$ 个人，第 $2k-1$ 个人和第 $2k$ 个人为一组（$k\in\mathbb{Z}_+$）。

每个人可以选择是否愿意合作，第 $i$ 个人选择愿意需要 $c_i$ 的代价，选择不愿意需要 $d_i$ 的代价，选择愿意但队友选择不愿意需要 $e_i$ 的额外代价。若两个人愿意合作，则可以选择合作或不合作。

有 $m$ 条单向关系，每条形如 $(A,B,a,b)$（保证 $A,B$ 互不为队友），表示：

• 若 $A$ 未与队友合作，且 $B$ 选择愿意合作，代价为 $a$。
• 若 $A$ 选择不愿意合作，且 $B$ 与队友合作，代价为 $b$。

求最小可能的代价总和。

$1\leq n\leq 5\times 10^3,0\leq m\leq 10^4$。

思路

最小割建模 trick 多合一。

首先如果没有“选择合作或不合作”一说，那么可以考虑下面一个建图（我们使用 $A_1,A_2$ 表示一组的两个组员）：

这个建模是十分经典的，将一个代表人的点划归 $c(S)$ 表示愿意合作，$c(T)$ 表示不愿意合作，如果同一组的两个人意愿不同，则必须割断 $A_1,A_2$ 间的某一条边。

现在我们需要加上选择合作的情况。由于选择合作必须两人都愿意合作，因此自然想到在 $T$ 一边扩展：

我们添加一个点 $A$。此时将 $A$ 划归 $c(S)$ 表示选择合作，否则表示不选择合作。如果不选择合作且 $(A_x,A)$ 在割集中，则表示 $A_x$ 愿意合作，否则不愿意。不过这要有一点小问题，我们会不会同时割断 $(S,A_1),(A,T)$？你发现这是有可能的！但这是不合法的，因为如果 $A_1$ 不愿意合作，则不可能选择合作，因此我们需要连接两条辅助边：

连边 $(A,A_1, \infty),(A,A_2,\infty)$ 相当于强制钦定不可能出现 $A$ 归属 $c(S)$，$A_1,A_2$ 归属 $c(T)$ 的情况，规避了上述不可能的情况。

现在来考虑单向关系。这里我们假设单项关系为 $(A_2,B_1,a,b)$。

对于【若 $A_2$ 未与队友合作，且 $B_1$ 选择愿意合作，代价为 $a$。】的情况，我们需要连边 $(B_1, A, a)$。这表示若 $B_1$ 位于 $c(S)$（即愿意合作），且 $A$ 位于 $c(T)$（即未合作）需要割断这条边。

同理，【若 $A_2$ 选择不愿意合作，且 $B_1$ 与队友合作，代价为 $b$】的情况，需要连边 $(B, A_1, b)$。

时间复杂度 $O(\mathrm{maxflow}(n, n+m))$，Submission。

PS：Google Gemini 2.5 Pro 提出了一个看起来可行的方法，不过太复杂了。

代码

#include <bits/stdc++.h>
using namespace std;

template<int N, int M, class Cap = int>
struct MaxFlow {
    struct node{
        int nxt, to;
        Cap cap;
    } g[M << 1];
    int head[N], ec, dep[N], cur[N], S, T;

    MaxFlow() : ec(1) {}

    void add(int u, int v, Cap c){
        g[++ec] = {head[u], v, c}, head[u] = ec;
        g[++ec] = {head[v], u, 0}, head[v] = ec;
    }

    bool bfs(){
        memset(dep, 0, sizeof(dep));
        queue<int> q;
        q.push(S), dep[S] = 1;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int i=head[u];i;i=g[i].nxt){
                int v = g[i].to;
                if(!dep[v] && g[i].cap) q.push(v), dep[v] = dep[u] + 1;
            }
        }
        return dep[T];
    }
    
    Cap dfs(int u, Cap flow){
        if(u == T) return flow;
        for(int &i=cur[u];i;i=g[i].nxt){
            int v = g[i].to;
            if(dep[v] == dep[u] + 1 && g[i].cap){
                Cap t = dfs(v, min(flow, g[i].cap));
                if(t) return g[i].cap -= t, g[i ^ 1].cap += t, t;
            }
        }
        return 0;
    }

    Cap operator()(int s, int t){
        S = s, T = t;
        Cap mxflow = 0;
        while(bfs()){
            memcpy(cur, head, sizeof(cur));
            Cap x = 0;
            while((x = dfs(S, numeric_limits<Cap>::max()))) mxflow += x;
        }
        return mxflow;
    }
};

const int N = 5005, M = 1e4 + 5;
MaxFlow<(N << 1) + N, (M << 1) + (N * 10), long long> mf;
int n, m;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    int S = 0, T = (n << 1) + n + 1;
    for(int i=1;i<=n;i++){
        int c1, d1, e1, c2, d2, e2, A = (i << 1) - 1, B = i << 1, P = (n << 1) + i;
        cin >> c1 >> d1 >> e1 >> c2 >> d2 >> e2;
        mf.add(S, A, d1), mf.add(S, B, d2);
        mf.add(A, P, c1), mf.add(B, P, c2);
        mf.add(P, A, 1e10), mf.add(P, B, 1e10);
        mf.add(P, T, c1 + c2);
        mf.add(A, B, e1), mf.add(B, A, e2);
    }
    for(int i=1;i<=m;i++){
        int u, v, a, b; cin >> u >> v >> a >> b;
        mf.add(v, (n << 1) + ((u + 1) >> 1), a), mf.add((n << 1) + ((v + 1) >> 1), u, b);
    }
    cout << mf(S, T) << '\n';
    return 0;
}

// Written by xiezheyuan