F. 特殊边 题解

题目大意

给定一张 $n$ 个点、$m$ 条边的有向图，每条边有一个容量 $w$（$0 \le w \le 25$）。其中前 $k$ 条边是"特殊边"，初始容量为 $0$。有 $q$ 次询问，每次询问给出 $k$ 个整数 $w_1, w_2, \dots, w_k$，表示将这 $k$ 条特殊边的容量分别设置为 $w_i$，问此时从 $1$ 到 $n$ 的最大流是多少。

数据范围：$2 \le n \le 10^4$，$1 \le m \le 10^4$，$1 \le k \le \min(10, m)$，$q \le 2 \times 10^5$。

---

解题思路

1. 最大流与最小割

根据最大流最小割定理，从 $1$ 到 $n$ 的最大流等于所有 $1$-$n$ 割的最小容量。一个割 $(S, T)$ 满足 $1 \in S$，$n \in T$，其容量为从 $S$ 指向 $T$ 的所有边的容量之和。

对于任意一个割，容量可以写成：

$$\text{cut}(S,T) = \text{base}(S,T) + \sum_{i=1}^{k} [\text{边 }i \text{ 从 }S\text{ 到 }T] \cdot w_i $$

其中 $\text{base}(S,T)$ 是普通边的贡献（与 $w_i$ 无关），$w_i$ 是第 $i$ 条特殊边的容量（询问时给定）。

---

2. 关键观察

由于 $k \le 10$，我们可以枚举哪些特殊边被包含在割中，用 $k$ 位二进制数 $mask$ 表示。

定义 $res[mask]$ 为：当所有 $i \in mask$ 的特殊边容量设为 $25$，其余特殊边容量设为 $0$ 时，从 $1$ 到 $n$ 的最大流。

这里 $25$ 是容量的最大值（题目保证 $w_i \le 25$），这样设置是为了"强制"这些边在最小割中可能会被选中（因为容量大）。

核心公式：对于询问 $(w_1,\dots,w_k)$，最大流等于：

$$\text{ans} = \min_{mask} \left( \sum_{i=1}^k w_i - \sum_{i \in mask} w_i + res[mask] \right) $$

推导：
对于询问，考虑一个割，它的特殊边割集是 $mask$。这个割的容量是 $\text{base}(S,T) + \sum_{i \in mask} w_i$。
在预处理中，$res[mask]$ 对应的是所有特殊边容量为 $0$ 或 $25$ 的情况，它等于 $\min_{割 \supseteq mask} (\text{base}(S,T) + \sum_{i \in mask} 25)$。
实际上，我们需要的是 $\min_{割} \left( \text{base}(S,T) + \sum_{i \in cut} w_i \right)$。可以证明这个最小值等于上式。

---

3. 如何计算 $res[mask]$

我们可以递推计算 $res[mask]$：

• $res[0]$：所有特殊边容量为 $0$ 时的最大流。
• 对于 $mask \neq 0$，设 $lowbit = mask \& -mask$，$prev = mask \oplus lowbit$。
  从 $prev$ 的状态出发，将 $lowbit$ 对应的特殊边容量从 $0$ 改为 $25$，然后继续增广。

为什么可以这样？因为最大流满足容量线性：当一条边的容量增加时，最大流的增量等于从 $1$ 到 $n$ 的增广路容量（不超过 $25$）。因此我们可以从上一次的最大流结果继续跑增广路，而不是重新跑整个网络流。

代码中的 FF(S) 函数会在当前残留网络上继续增广，返回增加的流量。所以 res[i] = res[prev] + FF(i)。

---

4. 回答询问

对于每个询问，读入 $w_1,\dots,w_k$，计算 $all = \sum w_i$，然后枚举所有 $mask$，用公式：

$$ans = \min_{mask} (all - \sum_{i \in mask} w_i + res[mask]) $$

其中 $\sum_{i \in mask} w_i$ 可以用递推 sum[mask] = sum[prev] + w[bit] 快速计算。

复杂度：$O(2^k \cdot (m + q))$，当 $k=10$ 时约为 $1024 \times (10^4 + 2\times 10^5) \approx 2\times 10^8$，在 5 秒内可以接受。

---

代码实现

// LUOGU_RID: 93970476
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
const int maxn=10005,maxm=20005,maxk=1<<10;
int n,m,k,Q,ans,e=1;
int lst[maxn],start[maxn],to[maxm],then[maxm],cur[maxn],sum[maxk],v[maxk],res[maxk],rec[maxm];
short limit[maxk][maxm],mn[maxn];
int q[maxn];

inline void add(int x,int y,int z){
    then[++e]=start[x],start[x]=e,to[e]=y,limit[0][e]=z;
}

inline void addedge(int x,int y,int z){
    add(x,y,z),add(y,x,0);
}

int bfs(int S){
    for(int i=1;i<=n;i++)
        lst[i]=mn[i]=0;
    int l=1,r=0;
    mn[1]=25,q[++r]=1;
    while(l<=r&&mn[n]==0){
        int x=q[l];
        l++;
        for(int i=start[x];i;i=then[i])
            if(limit[S][i]&&mn[to[i]]==0)
                mn[to[i]]=min(mn[x],limit[S][i]),lst[to[i]]=i,q[++r]=to[i];
    }
    if(lst[n]==0)
        return 0;
    int res=mn[n];
    for(int i=n;i!=1;i=to[lst[i]^1])
        limit[S][lst[i]]-=res,limit[S][lst[i]^1]+=res;
    ans+=res;
    return res;
}

int FF(int S){
    ans=0;
    while(bfs(S));
    return ans;
}

int main(){
    scanf("%d%d%d%d",&n,&m,&k,&Q);
    for(int i=1,x,y,z;i<=m;i++)
        scanf("%d%d%d",&x,&y,&z),addedge(x,y,z),rec[i]=e-1;
    
    // 预处理 res[0]
    res[0]=FF(0);
    
    // 递推计算所有 res[mask]
    for(int i=1;i<(1<<k);i++){
        int lst=i^(i&-i);  // 去掉最低位的1
        // 复制容量状态
        for(int j=2;j<=e;j++)
            limit[i][j]=limit[lst][j];
        // 将最低位对应的特殊边容量设为25
        limit[i][rec[__builtin_ctz(i&-i)+1]]=25;
        // 继续增广，得到 res[i]
        res[i]=res[lst]+FF(i);
    }
    
    // 处理询问
    for(int t=1;t<=Q;t++){
        int all=0,ans;
        for(int i=1;i<=k;i++)
            scanf("%d",&v[i]),all+=v[i];
        ans=all+res[0];
        for(int i=1;i<(1<<k);i++){
            sum[i]=sum[i^(i&-i)]+v[__builtin_ctz(i&-i)+1];
            ans=min(ans,all-sum[i]+res[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

---

代码说明

1. 存储结构：

   • limit[state][edge]：存储每个状态 $state$ 下每条边的剩余容量，使用 short 类型节省内存
   • rec[i]：存储第 $i$ 条特殊边在边数组中的位置（因为加了反向边，正向边下标为偶数）

2. Ford-Fulkerson 实现：

   • bfs(S)：BFS 找增广路，同时记录路径和瓶颈容量
   • FF(S)：不断调用 bfs 直到无法增广，返回本次增加的流量

3. 递推预处理：

   • 利用 lowbit 技巧枚举所有 $2^k$ 个状态
   • 每次只修改一条边的容量，在上一次残留网络上继续增广

4. 询问回答：

   • 枚举所有 $mask$，用递推计算 $\sum_{i \in mask} w_i$
   • 取最小值作为答案

---

时间复杂度

• 预处理：$O(2^k \cdot F)$，其中 $F$ 是每次增广的复杂度，由于容量 $\le 25$，增广次数有限
• 询问：$O(q \cdot 2^k)$，约 $2\times 10^5 \times 1024 \approx 2\times 10^8$，常数较小可通过

---

总结

本题的核心是利用 $k$ 很小的特点，预处理所有 $2^k$ 种特殊边容量极值状态下的最大流，然后对于每个询问通过枚举状态 $mask$ 快速计算答案。这是一种参数化最大流的经典处理方法，通过递推增广避免了重复计算。