P2057 善意的投票

二元选择的冲突数可以写成割的代价

问题

P2057 [SHOI2007] 善意的投票
每个人有希望投出的 $0/1$ 意见，但可为朋友妥协。总代价等于改变自身意愿的人数，加上实际意见不同的朋友对数；求最小总代价。

数据规模：$2\le n\le300$，$1\le m\le n(n-1)/2$。

这题没有明显的“流量”信号，不过每个人都只有 $0/1$ 两种最终状态。一次 $S-T$ 割恰好也会把所有普通点划分到源侧和汇侧两种状态中，因此可以尝试让割的两侧分别表示两种决策。

如果某个人改变了自己的意愿，或者某对朋友最终的意见不同，那么代价分别增加 $1$，问题也就可以抽象为：给每个点选择 $0$ 或者 $1$，使所有单点代价与相邻点冲突代价之和最小。

既然目标函数由若干局部代价之和组成，接下来就尝试让每一种局部代价恰好对应某条跨割边。只要一个方案对应一个割，并且割容量恰好等于方案总代价，原问题就转化成了最小割。

而一次 $S - T$ 割天然会把所有普通点分到两个集合中，因此可以直接赋予两侧决策的含义：点位于源侧，表示最终选择 $0$；反之位于汇侧，表示最终选择 $1$。

这样每一个割就对应一种完整投票方案。接下来只需要让这个割的容量恰好等于该方案产生的总代价。

从前面的代价出发，若某个人原本想投 $0$，那么只有它最终被分到汇侧，代价才记为 $1$，因此连接 $S \to i$ 容量为 $1$。反之若某个原本想投 $1$，情况是对称的，此时连接 $i\to T$，容量为 $1$。

还有一种情况是朋友之间不同的意见：对于一对朋友 $u,v$，只有两人的最终选择不同才需要支付 $1$。如果只连接一条 $u\to v$，那么只有 $u$ 在源侧、$v$ 在汇侧时会产生割代价，反过来却不会计数。因此需要双向各连一条容量为 $1$ 的边 $u \to v,\ v \to u$。

当 $u,v$ 位于不同侧时，恰好只有其中一条边从源侧指向汇侧，因此割容量恰好增加 $1$。

这一模型的核心在于：对于每个对象如果有两种决策状态，不妨先为割的两侧赋予决策含义。只要每个局部代价都能翻译成跨割代价，二元的全局选择就可以交给最小割来求解。

▶

P2057 建图

namespace DINIC { /* 模板代码略 */ }
using namespace DINIC;

void solve( ) {
    int n = read( ), m = read( );

    int S = 0, T = n + 1;
    init( T );

    for( int i = 1; i <= n; ++ i ) {
        int x = read( );
        if( x == 0 ) add_edge( S, i, 1 );
        else add_edge( i, T, 1 );
    }

    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        add_edge( u, v, 1 );
        add_edge( v, u, 1 );
    }

    cout << Dinic( S, T, T ) << '\n';
}