[六省联考 2017] 寿司餐厅

题目解析

🗑语文题
题目本身不是很难, 但是我花了大量的时间在理解题目在说什么尤其是一会种,一会份, 一会类

垃圾1: 如果包含了餐厅提供的从第 i 份到第 j 份的所有寿司, 量词和前面说的不统一

Kiana 一共吃过了 c (c>0) 种代号为 x 的寿司，则她需要为这些寿司付出 $mx^2 +cx$ 元钱
这个种原来意思是: 不同的代号为 x 的寿司🍣 的数量: 😡,浪费我1个小时

简化题目

这是一份去除了背景故事和干扰信息的极简题目描述：

核心模型

给定：

一个长度为 $n$ 的寿司序列，第 $i$ 个寿司有一个代号 $a_i$ 。
一个价值矩阵 $d_{i,j}$ （其中 $1 \le i \le j \le n$ ），表示区间 $[i, j]$ 的美味度。
一个常数 $m$ 。

操作： 你可以任意选择若干个区间 $[l, r]$ （可以重叠）。

收益计算（加法）：

对于任意一对 $(i, j)$ ，只要区间 $[i, j]$ 被你选择的任意一个区间完全覆盖，你就能获得 $d_{i,j}$ 的值。
注意：每个 $d_{i,j}$ 的值全场只能获得一次（即使被多个区间覆盖）。

成本计算（减法）：

按代号分类计算成本。
对于代号为 $x$ 的寿司，统计它在所有被选区间中出现的总次数 $c$ 。
该代号产生的成本为 $mx^2 + cx$ 。

目标： 最大化 (总收益 - 总成本)。

这里的关键逻辑图解 (Mermaid)

graph LR
    subgraph "1. 选择策略"
        A[选择区间 A: 1-2]
        B[选择区间 B: 2-3]
    end

    subgraph "2. 收益层 (每个 d 只算一次)"
        D11[获得 d_1,1]
        D22[获得 d_2,2]
        D33[获得 d_3,3]
        D12[获得 d_1,2]
        D23[获得 d_2,3]
        D13[d_1,3 未被完整覆盖, 不获得]
    end

    subgraph "3. 成本层 (按代号统计次数)"
        C1[代号 a_1 被选中 1 次<br>成本: m*a_1^2 + 1*a_1]
        C2[代号 a_2 被选中 2 次<br>成本: m*a_2^2 + 2*a_2]
        C3[代号 a_3 被选中 1 次<br>成本: m*a_3^2 + 1*a_3]
    end

    A --> D11 & D22 & D12
    B --> D22 & D33 & D23
  
    A --> C1 & C2
    B --> C2 & C3

    style D22 fill:#ff9,stroke:#333,stroke-width:2px,color:black
    style C2 fill:#f9f,stroke:#333,stroke-width:2px,color:black

图例解释：

黄色高亮：虽然区间 A 和 B 都覆盖了第 2 个寿司（ $d_{2,2}$ ），但收益只算一次。
粉色高亮：第 2 个寿司被选中了 2 次，这会增加代号 $a_2$ 的 $c$ 值（成本变高）。

解析

这道题 P3749 [六省联考 2017] 寿司餐厅 是一道非常经典的网络流（Network Flow）题目，具体来说，它是最大权闭合子图模型的一个精彩应用。

很多同学看到这种“选这个就必须选那个”、“收益减去代价”的题目，通过 DP 很难处理（因为状态太复杂），这时候就要往最小割的方向去想。

下面我们一步步拆解这道题。

1. 核心模型：最大权闭合子图

首先，我们要把题目翻译成图论模型。题目要求我们做一系列选择，每个选择都有对应的权值（有正有负），并且选择之间存在依赖关系。

目标：最大化（总收益 - 总花费）。
转化：这等价于 所有正收益之和 - 最小割（最小损失）。

在最小割模型中：

我们从源点 $S$ 向代表“正收益”的物品连边，容量为收益值。
从代表“负收益（成本）”的物品向汇点 $T$ 连边，容量为成本的绝对值。
如果物品 A 依赖于物品 B（选 A 必选 B），则从 A 向 B 连一条容量为 $\infty$ 的边（表示割不断，即这种依赖关系必须满足）。

2. 题目中的依赖关系分析

这道题的难点在于如何正确地建立依赖图。我们需要分析出题目中隐含的三层结构。

第一层：区间的依赖 (金字塔结构)

题目定义了 $d_{i, j}$ 。为了拿到区间 $[i, j]$ 的美味度（假设 $i < j$ ），意味着你必须吃了这一段寿司。逻辑上，我们可以这样定义依赖：

要想拥有区间 $[i, j]$ 的加成，你必须拥有子区间 $[i+1, j]$ 和 $[i, j-1]$ 的加成。
这样一直递归下去，最终会依赖到单点 $[i, i], [i+1, i+1] \dots [j, j]$ 。

这里是区间DP,也是这个题目的难点!!

为什么要这样连边？ 如果直接从 $[i, j]$ 连向所有 $[k, k]$ ( $i \le k \le j$ )，边数会达到 $O(N^3)$ ，太多了。通过 $[i, j] \to [i+1, j]$ 和 $[i, j] \to [i, j-1]$ ，我们只需要 $O(N^2)$ 的边就能间接覆盖所有依赖。

第二层：单点寿司的依赖与成本拆解

对于单点寿司 $i$ ，它的收益是 $d_{i, i}$ ，但它也有成本。题目说：吃了 $c$ 个代号为 $x$ 的寿司，花费 $mx^2 + cx$ 。我们可以把花费拆开：

固定花费（门票费）：只要你吃了代号为 $x$ 的寿司（无论吃几个），就要付 $mx^2$ 。
按量花费：每吃一种代号为 $x$ 的寿司，要多付 $x$ 元。

这里最难理解的就是这个 $C\times x$ ,比如有第1种,第2种寿司,代码都是1, 那么分别吃了3,4 个,那么这里的C 是 $2$ ,因为吃了2种代号为 1 的寿司

处理策略：

对于单点节点 $(i, i)$ ，它的净收益修正为： $d_{i, i} - a_i$ 。
- 因为 $cx$ 这一项是线性的，可以直接分摊到每个寿司头上。
如果修正后的 $d_{i, i} - a_i$ 是正的，连 $S$ ；如果是负的，连 $T$ 。

第三层：类型（代号）的依赖

如果你选择吃第 $i$ 个寿司（代号为 $a_i$ ），那么你必须支付该代号的“门票费” $m \cdot a_i^2$ 。

我们需要为每一种寿司代号（Type）建立一个独立的节点。
单点寿司节点 $(i, i)$ 连向对应的 代号节点，容量 $\infty$ 。
代号节点 向 $T$ 连边，容量为 $m \cdot a_i^2$ 。

3. 图解构建 (Mermaid)

让我们把这三层结构画出来，帮助理解。假设我们有 3 个寿司，代号分别是 1, 2, 1。

graph TD
    S((源点 S))
    T((汇点 T))

    subgraph "区间加成 (d_ij)"
        d13["[1,3]"]
        d12["[1,2]"]
        d23["[2,3]"]
    end

    subgraph "单点寿司 (d_ii - a_i)"
        p1["寿司1 (ID:1)"]
        p2["寿司2 (ID:2)"]
        p3["寿司3 (ID:1)"]
    end

    subgraph "代号成本 (mx^2)"
        type1["代号 1"]
        type2["代号 2"]
    end

    %% 正收益连 S (假设 d_ij > 0)
    S -->|d_1,3| d13
    S -->|d_1,2| d12
    S -->|d_2,3| d23
  
    %% 假设单点净收益 > 0 连 S， < 0 连 T (这里简略画)
    S -.-> p1
    S -.-> p2
    S -.-> p3

    %% 区间依赖
    d13 -->|inf| d12
    d13 -->|inf| d23
    d12 -->|inf| p1
    d12 -->|inf| p2
    d23 -->|inf| p2
    d23 -->|inf| p3

    %% 类型依赖
    p1 -->|inf| type1
    p2 -->|inf| type2
    p3 -->|inf| type1

    %% 类型成本连 T
    type1 -->|m*1^2| T
    type2 -->|m*2^2| T

4. 详细连边规则总结

节点编号：
- 源点 $S$ ，汇点 $T$ 。
- 区间节点 $(i, j)$ ：可以用二维转一维的映射函数 id(i, j) 给每个区间分配一个编号。
- 代号节点 $Type_x$ ：为出现过的每个代号 $x$ 分配一个编号（代号范围 1~1000）。
构建边的逻辑：
- 对于每个区间 $(i, j)$ (其中 $i < j$ )：
  - 若 $d_{i, j} > 0$ ：连边 $S \to id(i, j)$ ，容量 $d_{i, j}$ 。
  - 若 $d_{i, j} < 0$ ：连边 $id(i, j) \to T$ ，容量 $-d_{i, j}$ 。（作为一种必须支付的惩罚成本，虽然逻辑上一般这类区间不会被选，但如果被更大的正收益区间包含，则必须选）。
  - 依赖：连边 $id(i, j) \to id(i+1, j)$ ，容量 $\infty$ 。
  - 依赖：连边 $id(i, j) \to id(i, j-1)$ ，容量 $\infty$ 。
- 对于每个单点 $(i, i)$ ：
  - 计算权值 $W = d_{i, i} - a_i$ 。
  - 若 $W > 0$ ：连边 $S \to id(i, i)$ ，容量 $W$ 。
  - 若 $W < 0$ ：连边 $id(i, i) \to T$ ，容量 $-W$ 。
  - 依赖：连边 $id(i, i) \to TypeNode(a_i)$ ，容量 $\infty$ 。
- 对于每个代号节点 $Type_x$ ：
  - 连边 $TypeNode(x) \to T$ ，容量 $m \cdot x^2$ 。
最终答案：
- Answer = 所有正权值之和 - 最大流(最小割)。

5. 容易忽略的细节 (避坑指南)

作为老师，我要提醒你几个写代码时容易出错的地方：

总收益的统计：在建图之前，你需要把所有 $d_{i, j} > 0$ 的值加起来作为“理论最大收益”。注意，对于单点 $(i, i)$ ，如果 $d_{i, i} - a_i > 0$ ，也要加进这个总和里。如果是负的，就不加，而是作为图中的流量（代价）处理。
$d_{i, j}$ 为负数的情况：
- 如果 $d_{i, j}$ 是负的，它不贡献正收益，反而变成了选择该区间的一个“代价”。
- 所以它应该像成本一样：从节点连向 $T$ ，容量为 $|d_{i, j}|$ 。
- 这一点很容易漏掉，很多同学只处理了正收益的 $d_{i, j}$ 。
节点数量估算：
- $N \le 100$ 。
- 区间节点数 $\approx N^2/2 \approx 5000$ 。
- 代号节点数 $\approx 1000$ 。
- Dinic 算法跑这个规模是完全没问题的。
$m=0$ 的情况：
- 题目数据范围里有 $m=0$ 的情况。虽然公式 $mx^2$ 算出来是 0，代码逻辑通用，但要注意如果你的建图逻辑里依赖了 $m$ 来判断是否建点，不要特判漏了。建议统一处理，容量为 0 的边自然会被算法处理掉（或者优化掉不建这个边）。
代号 $a_i$ 的范围：
- $a_i$ 最大是 1000，不要用 $N$ 去开代号节点的数组，要用 $\max(a_i)$ 。

6. 总结

这道题是 最大权闭合子图 的进阶版。解题的关键在于：

拆分成本：将 $mx^2 + cx$ 拆分为“类型固定成本”和“单点线性成本”。
构建依赖：利用 $d_{i, j}$ 的包含关系建立 $O(N^2)$ 的金字塔依赖图。
转化问题：利用最小割求解最大收益。

希望这个解析能帮你理清思路！如果理解了，就去尝试写一下代码吧。加油！

代码

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-28 14:04:07
 */

#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 a[105];         // 寿司代号
int d[105][105];    // 美味度
int id[105][105];   // 区间[i,j]对应的图节点编号
int type_id[1005];  // 代号x对应的图节点编号
int s, t;           // 源点 汇点

// 存图的模板
//oisnip_begin code/graph/linklist.cpp 内容开始
struct linkList {
    typedef struct {int u,v; long long w; int next;} edge; // 修改: w改为long long防溢出
    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,long long w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    void add2(int u,int v,long long w=0){
        add(u,v,w);
        add(v,u,w);
    }
    //下标访问
    edge& operator[](int i){ return e[i]; }

#ifdef __cpp_range_based_for
    struct UseEdge {
        using ReturnType = edge&; 
        static ReturnType get(linkList* p, int i) { return p->e[i]; }
    };
    struct UseAdj {
        using ReturnType = int;   
        static ReturnType get(linkList* p, int i) { return p->e[i].v; }
    };
    template<typename Getter>
    struct BaseIterator {
        int i;          
        linkList* p;    
        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; }
        typename Getter::ReturnType operator*() { return Getter::get(p, i); }
    };
    using Iterator    = BaseIterator<UseEdge>;
    using AdjIterator = BaseIterator<UseAdj>;
    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); }
    };
    BaseRange<Iterator> operator()(int u) { return BaseRange<Iterator>(this, 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;  
    int n;  
  
    void init(int n) {
        e.edge_cnt = 0;
        memset(e.h, -1, sizeof(e.h));
        level.resize(n+5);
        cur.resize(n+5);
        this->n = n;
    }
  
    void addEdge(int u, int v, long long cap) {
        e.add(u, v, cap);    
        e.add(v, u, 0);      
    }
  
    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();
          
            for(int i = e.h[u] ; ~i ;i = e[i].next) {
                int v = e[i].v;
                long long cap = e[i].w;
                if (cap > 0 && level[v] < 0) {
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        return level[t] >= 0;  
    }
  
    long long dfs(int u, int t, long long preFlow) {
        if (u == t || preFlow == 0) return preFlow;
        long long flow = 0;
      
        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;
    }
  
    long long maxFlow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {  
            for (int i = 0; i <= n; i++) {
                cur[i] = e.h[i];  
            }
            flow += dfs(s, t, INF); // 修改: 使用 long long INF
        }
        return flow;
    }
} dinic;

// 全局变量用于统计所有正权值的总和
long long total_positive_weight = 0;

void init(){
    // 1. 输入处理
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            cin >> d[i][j];
        }
    }

    // 2. 节点编号分配
    // S=0, T由最后决定
    // 1..CNT 为区间节点
    // 之后为代号节点
    int node_cnt = 0;
    
    // 给所有区间 [i,j] 分配节点ID
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            id[i][j] = ++node_cnt;
        }
    }
    
    // 给所有出现的代号分配节点ID
    // 代号范围是1-1000，可以用数组映射
    memset(type_id, 0, sizeof(type_id));
    for(int i = 1; i <= n; i++){
        if(type_id[a[i]] == 0) {
            type_id[a[i]] = ++node_cnt;
        }
    }

    s = 0;
    t = node_cnt + 1;
    dinic.init(t); // 初始化Dinic，大小为总节点数

    // 3. 建图 (最大权闭合子图模型)
    
    // 处理区间节点
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            int u = id[i][j];
            int val = d[i][j];
            
            // 特殊处理单点：减去常数项成本 a[i]
            // 题目公式成本 = m*x^2 + c*x。
            // 这里处理 c*x 部分：每吃一种代号为x的寿司，就减去x
            if(i == j) {
                val -= a[i];
            }

            // 正权连S，负权连T
            if(val > 0) {
                total_positive_weight += val;
                dinic.addEdge(s, u, val);
            } else if(val < 0) {
                dinic.addEdge(u, t, -val);
            }

            // 建立依赖关系 (无穷大边)
            if(i < j) {
                // 区间 [i,j] 依赖于 [i+1, j] 和 [i, j-1]
                // 选了父必须选子 -> 父连向子
                dinic.addEdge(u, id[i+1][j], INF);
                dinic.addEdge(u, id[i][j-1], INF);
            } else if(i == j) {
                // 单点 [i,i] 依赖于它的代号节点
                // 选了该寿司，必须支付该代号的固定成本 mx^2
                dinic.addEdge(u, type_id[a[i]], INF);
            }
        }
    }

    // 处理代号节点
    // 只要选择了某个代号的寿司（无论多少个），都要支付 mx^2
    // 代号节点连向 T，容量为 mx^2 (这是成本)
    // 这里的 x 就是代号值
    for(int x = 1; x <= 1000; x++){
        if(type_id[x]) {
            int u = type_id[x];
            long long cost = (long long)m * x * x;
            dinic.addEdge(u, t, cost);
        }
    }
}

// 使用示例：
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    init();
    
    // 最大权闭合子图结论：最大收益 = 所有正权值之和 - 最小割(最大流)
    long long max_profit = total_positive_weight - dinic.maxFlow(s, t);
    
    cout << max_profit << "\n";
  
    return 0;
}