Description

给定一张 \(n \le 300\) 个点，\(m\) 条边的图，每个点有一个初始的颜色 \(a[i]=0/1\)，你可以翻转一些点的颜色，最小化翻转的点的数量与连接不同颜色的边的数目的总和。

Solution

最小割模型，对于原图中两个有边相连的点连一条边，\(S \to 0, T \to 1\)，边权都是 \(1\)。

#include <bits/stdc++.h>
using namespace std;
const int N = 16384, MAXN = 262144;
#define reset(x) memset(x, 0, sizeof x)
struct graph
{
    int n, m, M, S, T, head[N], cur[N], dep[N], gap[N], q[N];
    long long ans;
    struct ed
    {
        int to, nxt, val;
    } edge[MAXN];
    void init(int n0, int m0, int S0, int T0)
    {
        n = n0, m = m0, S = S0, T = T0, M = 1, reset(gap);
        reset(head), reset(cur), reset(dep), reset(q);
    }
    void _make(int u, int v, int w)
    {
        edge[++M] = (ed){v, head[u], w}, head[u] = M;
    }
    void make(int u, int v, int w)
    {
        _make(u, v, w);
        _make(v, u, 0);
    }
    int dfs(int u, int mx)
    {
        if (u == T)
            return mx;
        int num = 0, f;
        for (int &i = cur[u], v; i; i = edge[i].nxt)
            if (dep[v = edge[i].to] == dep[u] - 1 && (f = edge[i].val))
                if (edge[i].val -= (f = dfs(v, min(mx - num, f))), edge[i ^ 1].val += f, (num += f) == mx)
                    return num;
        if (!--gap[dep[u]++])
            dep[S] = n + 1;
        return ++gap[dep[u]], cur[u] = head[u], num;
    }
    void solve()
    {
        for (int i = 1; i <= n; ++i)
            cur[i] = head[i];
        ans = 0;
        for (gap[0] = n; dep[S] <= n; ans += dfs(S, 0x7fffffff))
            ;
    }
} g;

// init
// make
// solve

signed main()
{
    int n, m;
    cin >> n >> m;

    auto id_source = [&](void) -> int {
        return 1;
    };
    auto id_target = [&](void) -> int {
        return 2;
    };
    auto id_vertex = [&](int x) -> int {
        return 2 + x;
    };

    g.init(n + 2, 0, id_source(), id_target());

    for (int i = 1; i <= n; i++)
    {
        int t;
        cin >> t;
        if (t == 0)
        {
            g.make(id_source(), id_vertex(i), 1);
        }
        else
        {
            g.make(id_vertex(i), id_target(), 1);
        }
    }

    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        g.make(id_vertex(u), id_vertex(v), 1);
        g.make(id_vertex(v), id_vertex(u), 1);
    }

    g.solve();

    cout << g.ans << endl;
}