题解：CF1666K Kingdom Partition

考虑一条边两个端点

u

和

v

所在集合的贡献系数：

	$A$	$B$	$C$
$A$	$2$	$0$	$1$
$B$	$0$	$2$	$1$
$C$	$1$	$1$	$2$

我们发现这和“两集选一”问题看起来相似，考虑最小割，但是这是“三集选一”，源点和汇点仅能刻画两种状态，于是我们将一个点

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$	$ST$	$TS$	$TT$
$SS$	$0$	$1$	$1$	$2$
$ST$	$1$	$2$	$0$	$1$
$TS$	$1$	$0$	$2$	$1$
$TT$	$2$	$1$	$1$	$0$

我们惊奇的发现：

	$ST$	$TS$	$TT$
$ST$	$2$	$0$	$1$
$TS$	$0$	$2$	$1$
$TT$	$1$	$1$	$0$

以及

	$TS$	$ST$	$SS$
$TS$	$2$	$0$	$1$
$ST$	$0$	$2$	$1$
$SS$	$1$	$1$	$0$

与最开头给出的系数完全相同。同时我们又发现选

SS

和选

TT

本质相同，换而言之我们可以将所有

TT

换成

SS

，所以

SS

和

TT

间的

2

系数在最小割中会被忽略。

综上所述，我们对

u_1, u_2

分别做“两集选一”即可，时间复杂度是最大流的

\mathcal{O}(n^2m)

。

Code：

CPP

#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;
}

题解：CF1666K Kingdom Partition

文章操作

相关推荐

评论

题解：CF1666K Kingdom Partition