[SHOI2007] 善意的投票 / [JLOI2010] 冠军调查

题目解析

思考:
核心: 有冲突,怎么选冲突最小

算样例

如果不考虑朋友的限制, 那么这个题目就是贪心: 答案恒等于0
但是要考虑和朋友选的是否一样

!! 💡 考虑到最简单的情况: 发现只有a b 两个人是朋友且选则不一样的时候才会有冲突 !!!

flowchart LR
    a === b
    subgraph "不睡觉😄"
    a
    end

    subgraph "睡觉🛌"
    b
    end

证明:

$p$ : a,b 不是好朋友,则 a,b 不可能发生冲突
$q$ : a,b 是好朋友且 a,b的选择一样,则 a,b 不可能发生冲突

显然: $p \lor q$ 则 a,b 不可能发生冲突,
$\neg (p \lor q) \Leftrightarrow \neg p \land \neg q$ ??? 这里有问题

这道题的本质是一个二者择一的最小化问题，在离散数学中，这对应于布尔格（Boolean Lattice）的划分问题。

🧠 离散数学模块：理解题目本质

1. 逻辑算子与集合划分

我们将 $n$ 个小朋友映射为集合 $V = \{x_1, x_2, \dots, x_n\}$ 。每个小朋友的状态是一个布尔变量 $v_i \in \{0, 1\}$ 。

既然是二元选择,那么选择后肯定是两个集合

定义两个相互排斥的集合（划分为两个等价类）：

$S = \{x_i \mid v_i = 1\}$ (最终决定睡觉的人)
$T = \{x_i \mid v_i = 0\}$ (最终决定不睡觉的人)

2. 冲突函数的谓词逻辑表示

题目定义的“冲突数” $C$ 是两个谓词逻辑项的并集：

意愿背离项 ( $C_1$ ): $\sum_{i=1}^n [v_i \neq \text{original}_i]$
- 若原本想睡 ( $1$ ) 却归入 $T$ ，或原本不想睡 ( $0$ ) 却归入 $S$ ，产生 $1$ 单位代价。
朋友矛盾项 ( $C_2$ ): $\sum_{(i,j) \in E} [v_i \neq v_j]$
- 若 $(i,j)$ 是朋友且被划分到了不同的集合 ( $S$ 和 $T$ )，产生 $1$ 单位代价。

3. 修正你的逻辑推导

你提到的 $\neg (p \lor q)$ 只是揭示了“朋友间产生冲突”的条件。要推导出最小割模型，我们需要构建一个耗散函数 (Cost Function)。

设 $A$ 为原意愿为 1 的集合， $B$ 为原意愿为 0 的集合。

最小化目标：

min \left( \sum_{i \in A} [x_i \in T] + \sum_{j \in B} [x_j \in S] + \sum_{(u,v) \in E} [u \in S \land v \in T \text{ or } u \in T \land v \in S] \right)

这在图论中完美对应了源点 $S$ （代表 1）与汇点 $T$ （代表 0）之间的割。

📊 动态训练营：模型转换 (Min-Cut)

为了最小化冲突，我们构造如下容量网络：

意愿约束：
- 若小朋友 $i$ 意愿为 $1$ ：连边 $(S, i)$ ，容量为 $1$ 。割断此边表示“背离意愿”，代价为 $1$ 。
- 若小朋友 $i$ 意愿为 $0$ ：连边 $(i, T)$ ，容量为 $1$ 。割断此边表示“背离意愿”，代价为 $1$ 。
关系约束：
- 若 $i, j$ 是朋友：连双向边 $(i, j)$ ，容量为 $1$ 。
- 关键逻辑：一旦 $i \in \text{源点集}$ 且 $j \in \text{汇点集}$ （即两人选得不一样），跨越切口的边 $(i, j)$ 就会被计入割。

📶 信号反射 & 思维模板

1. 关键信号 (Key Signals)

二元选择：题目要求在两个对立的状态（睡觉/不睡觉）中做出选择。
最小化损失/冲突：这种“代价最小化”且带有“约束关联”的特征是典型的最小割信号。
关系边：朋友关系 $(i,j)$ 产生的代价与绝对位置无关，仅与 $i, j$ 是否属于同一集合有关。

2. 逻辑跃迁 (Logic Jump)

从“好朋友选择不同产生冲突”转换到“图的切分”。

直觉：把“睡觉”看作南极，“不睡觉”看作北极。
跃迁点：我们要把所有点拉向两极。如果一对朋友被拉向了不同的极点，他们之间的连线就会被“撕断”。撕断连线所需的力（容量）就是冲突代价。

3. 模式识别 (Pattern Recognition)

以后看到 “ $n$ 个元素做二选一决策 + 元素间存在违背关系的成本 + 元素自身选择的固有成本”，本能反应就应该是 “最小割 (Min-Cut = Max-Flow)”。

教练点评：

你对离散数学的敏感度很高。记住，在这种题目里，“冲突”等价于“割边”。逻辑推导的终点应该是证明：每一个合法的投票方案都唯一对应图的一个割，且方案的冲突数等于割的容量。

我的最终理解

最小化

min \left( \sum_{i \in A} [x_i \in T] + \sum_{j \in B} [x_j \in S] + \sum_{(u,v) \in E} [u \in S \land v \in T \text{ or } u \in T \land v \in S] \right)

flowchart LR
  S --- u
  subgraph 集合-不想睡
  u
  end
  subgraph 集合-想睡
  v1
  v2
  end

  u---v1 --- T
  u---v2 --- T

每次都要做选择
1. u,v 选择哪个集合
2. 朋友是否在用一个集合
割完美映射了选择

“冲突”等价于“割边”。逻辑推导的终点应该是证明：每一个合法的投票方案都唯一对应图的一个割，且方案的冲突数等于割的容量。

📶 信号反射 & 思维模板

关键信号 (Key Signals)：
- “ $N$ 个点二选一”、“最小冲突数”、“朋友/邻居间限制”。
- 数据范围 $N \le 300$ ，这是明显的网络流复杂度信号。
逻辑跃迁 (Logic Jump)：
- 看到“不同则产生代价”，立刻联想到切断连接两个不同状态集合的边。
- 将原本的意愿视为与源/汇点的“引力”，将朋友关系视为点与点之间的“粘性”。
模式识别 (Pattern Recognition)：
- 以后看到 “二元状态分配 + 违背意愿代价 + 邻接状态冲突代价”，本能反应就应该是 “最小割建模， $S$ 连意愿 $1$ ， $T$ 连意愿 $0$ ，朋友连双向边”。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-25 10:07:50
 */

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5; // 点
const int maxe = 2e6+5; // 边 (注意：要是题目边数的2倍)
const long long INF = 1e18;

int n,m;
int s,t; // 源点 汇点
int a[maxn];

// 存图的模板

//oisnip_begin code/graph/linklist.cpp 内容开始

// const int maxn = 1e6+5;
// const int maxe = 1e6+5;

struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        reset();
    }

    void reset() {
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    void add2(int u,int v,int w=0){
        add(u,v,w);
        add(v,u,w);
    }
    //下标访问
    edge& operator[](int i){ return e[i]; }

    // 参考 语法糖
    // https://en.cppreference.com/w/cpp/language/range-for.html
#ifdef __cpp_range_based_for
    // C++ 模板 和 策略模式（Policy） 来消除重复代码。
    // 我们可以定义一个通用的迭代器模板，通过传入不同的“提取器（Getter）”来决定 operator* 返回什么。
    // === 1. 定义数据提取策略 (核心区别) ===
    
    // 策略A: 获取整条边 (对应原本的 Iterator)
    struct UseEdge {
        using ReturnType = edge&; // 定义返回类型
        static ReturnType get(linkList* p, int i) { return p->e[i]; }
    };

    // 策略B: 只获取邻接点v (对应原本的 AdjIterator)
    struct UseAdj {
        using ReturnType = int;   // 定义返回类型
        static ReturnType get(linkList* p, int i) { return p->e[i].v; }
    };

    // === 2. 通用迭代器模板 (复用逻辑) ===
    template<typename Getter>
    struct BaseIterator {
        int i;          // 边的编号
        linkList* p;    // linkList指针
        
        BaseIterator(linkList* p, int i) : p(p), i(i) {}

        // 通用的遍历逻辑
        BaseIterator& operator++() { i = p->e[i].next; return *this; }
        bool operator!=(const BaseIterator& oth) { return i != oth.i; }
        
        // 差异化逻辑：委托给 Getter 处理
        typename Getter::ReturnType operator*() { return Getter::get(p, i); }
    };

    // 定义具体的迭代器别名
    using Iterator    = BaseIterator<UseEdge>;
    using AdjIterator = BaseIterator<UseAdj>;

    // === 3. 通用范围类模板 ===
    template<typename IterT>
    struct BaseRange {
        int start;
        linkList* p;
        BaseRange(linkList* p, int start) : p(p), start(start) {}
        IterT begin() { return IterT(p, p->h[start]); }
        IterT end()   { return IterT(p, -1); }
    };

    // === 4. 接口语法糖 ===
    
    // usage: for(auto& e : list(u))
    BaseRange<Iterator> operator()(int u) { return BaseRange<Iterator>(this, u); }

    // usage: for(int v : list.adj(u))
    BaseRange<AdjIterator> adj(int u) { return BaseRange<AdjIterator>(this, u); }
    
#endif
} e;

//oisnip_end code/graph/linklist.cpp 内容结束


// Dinic算法最大流模板 - 基于linkList存图
struct Dinic {
    vector<int> level, cur;  // level: BFS分层, cur: 当前弧优化
    int n;  // 节点数
    
    void init(int n) {
        // 重置linkList
        e.edge_cnt = 0;
        memset(e.h, -1, sizeof(e.h));

        level.resize(n+5);
        cur.resize(n+5);
        this->n = n;
    }
    
    // 添加边：从u到v，容量为cap
    // 使用技巧：正向边和反向边的索引相差1，通过异或1来找到对应边
    void addEdge(int u, int v, int cap) {
        e.add(u, v, cap);    // 正向边，w字段存储容量
        e.add(v, u, 0);      // 反向边，容量为0
    }
    
    // BFS分层，构建层次图
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            // 使用linkList的遍历方式
            for(int i = e.h[u] ; ~i ;i = e[i].next) {
                int v = e[i].v, cap = e[i].w;
                if (cap > 0 && level[v] < 0) {
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        
        return level[t] >= 0;  // 返回是否能到达汇点
    }
    
    // DFS寻找增广路
    // 到达点u流量为preFlow
    // 计算从点u出发的最大流，到达点t
    // 本质是一个DAG 上的dp
    long long dfs(int u, int t, long long preFlow) {
        if (u == t || preFlow == 0) return preFlow;
        long long flow = 0;
        
        // 当前弧优化：从cur[u]开始遍历
        for (int& cid = cur[u]; cid != -1; cid = e[cid].next) {
            auto& edge = e[cid]; // 当前弧优化
            int to = edge.v;
            long long cap = edge.w;
            
            if (level[u] + 1 != level[to] || cap <= 0) continue;
            
            long long tr = dfs(to, t, min(preFlow, cap));

            // 更新容量
            e[cid].w -= tr ;     // 正向边容量减少
            e[cid ^ 1].w += tr; // 反向边容量增加（利用异或找到反向边）
            flow += tr;
            preFlow -= tr;
            if (preFlow == 0) break;
        }
        
        // 炸点优化
        // 剪枝：取掉增广完毕的点
        if (flow == 0) level[u] = -1;
        return flow;
    }
    
    // 求从s到t的最大流
    long long maxFlow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {  // 能够分层
            // 当前弧优化重置：将cur设置为每个节点的第一条边
            for (int i = 0; i <= n; i++) {
                cur[i] = e.h[i];  // 使用linkList的operator()获取head[i]
            }
            
            // 多路增广
            flow += dfs(s, t, LLONG_MAX);
        }
        return flow;
    }
} dinic;

void init(){
    std::cin >> n >> m;
    s = 0;
    t = n+1;

    dinic.init(t+5);
    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        int sleep;
        std::cin >> sleep;

        if( sleep ) {
            dinic.addEdge(s, i, 1);
        }
        else
            dinic.addEdge(i, t, 1);

    }
    for(int i = 1;i <= m ;++i ) // i: 1->m
    {
        int u,v;
        std::cin >> u >> v;
        dinic.addEdge(u, v, 1);
        dinic.addEdge(v,u,1);
    }

}

// 使用示例：
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    init();
    
    cout << dinic.maxFlow(s,t) << "\n";
    
    return 0;
}

/*
复杂度分析：
- 时间复杂度：O(V²E) 一般情况下表现很好，对于单位容量网络是O(min(V^(2/3), E^(1/2)) * E)
- 空间复杂度：O(V + E)

使用说明：
1. 创建Dinic实例：Dinic dinic(n);
2. 添加边：dinic.addEdge(u, v, cap);
3. 求最大流：long long flow = dinic.maxFlow(source, sink);

注意事项：
- 节点编号从0开始
- 如果题目给的是1-indexed，记得转换
- 容量使用long long防止溢出
- 无向边需要添加两条有向边
*/