题解：CF1666K Kingdom Partition

Claire0918 · 2025-10-10 20:43:30 · 题解

考虑一条边两个端点 u 和 v 所在集合的贡献系数：

我们发现这和“两集选一”问题看起来相似，考虑最小割，但是这是“三集选一”，源点和汇点仅能刻画两种状态，于是我们将一个点 u 拆成两个点 u_1, u_2，并声称若 u_1 在源点一侧且 u_2 在汇点一侧则 u 在 A 中，若 u_1 在汇点一侧且 u_2 在源点一侧则 u 在 B 中，否则 u 在 C 中。我们将原图中的边 (u, v) 变为 (u_1, v_2), (u_2, v_1)，再考量 u_1, u_2 和 v_1, v_2 所在集合的贡献系数：

我们惊奇的发现：

以及

与最开头给出的系数完全相同。同时我们又发现选 SS 和选 TT 本质相同，换而言之我们可以将所有 TT 换成 SS，所以 SS 和 TT 间的 2 系数在最小割中会被忽略。

综上所述，我们对 u_1, u_2 分别做“两集选一”即可，时间复杂度是最大流的 \mathcal{O}(n^2m)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 1000 + 10, maxm = 2000 + 10, maxv = maxn << 1;

struct{
    int v, nex;
    long long w;
} edge[maxm << 3];

int n, m, s, t, a, b;
long long flow = 0;
int dep[maxv];
bitset<maxv> res;
int head[maxv], hd[maxv], top = 1;

inline void add(int u, int v, long long w, bool o = true){
    edge[++top].v = v, edge[top].w = w, edge[top].nex = head[u], head[u] = top, o && (add(v, u, 0, false), 1538);
}

inline bool bfs(){
    queue<int> q;
    q.push(s), mem(dep, 0), dep[s] = 1;
    while (!q.empty()){
        const int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = edge[i].nex){
            const int v = edge[i].v;
            const long long w = edge[i].w;
            w && !dep[v] && (q.push(v), dep[v] = dep[u] + 1);
        }
    }
    return dep[t];
}

inline long long dfs(int u, long long fl){
    if (u == t){
        return fl;
    }
    long long sum = 0;
    for (int &i = hd[u]; i; i = edge[i].nex){
        const int v = edge[i].v;
        const long long w = edge[i].w;
        if (dep[v] == dep[u] + 1 && w){
            const long long f = dfs(v, min(w, fl));
            edge[i].w -= f, edge[i ^ 1].w += f, sum += f, fl -= f;
            if (!fl){
                break;
            }
        }
    }
    return sum;
}

inline void dfs2(int u){
    res.set(u);
    for (int i = head[u]; i; i = edge[i].nex){
        const int v = edge[i].v;
        const long long w = edge[i].w;
        w && !res.test(v) && (dfs2(v), 1538);
    }
}

int main(){
    scanf("%d %d %d %d", &n, &m, &a, &b), s = n << 1 | 1, t = s + 1, add(s, a, 1e18), add(a + n, t, 1e18), add(s, b + n, 1e18), add(b, t, 1e18);
    while (m--){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w), add(u, v + n, w), add(u + n, v, w), add(v + n, u, w), add(v, u + n, w);
    }
    while (bfs()){
        memcpy(hd, head, sizeof(head)), flow += dfs(s, 1e18);
    }
    printf("%lld\n", flow), dfs2(s);
    for (int i = 1; i <= n; i++){
        putchar(res.test(i) && !res.test(i + n) ? 'A' : !res.test(i) && res.test(i + n) ? 'B' : 'C');
    }

return 0;
}