题解：P5192 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流

· · 题解

0.前言

开开心心地打开题目
啊？竟然没有用 ISAP 的题解
谔谔谔谔谔
为了让自己理解深刻，也为了广大用 ISAP 的OIer，吾辈义不容辞

1.思路

以上的题解已经说的恒清楚了，想看的看吧，我就献丑了

引入

本题其实就是【模板】网络最大流的加强版。
在【模板】网络最大流中，每条边的流量的取值范围为 [0,r]
而在本题中，取值范围为 [l,r]
多了个下界，怎么办捏？
不难想到：把能流的流一遍，不就变成网络最大流了吗？

想法很丰满，but显然流量不平衡了！
也就是说，有的点凭空流出了流量，但是又有流量流入点之后消失了。
不过，为了防止我们还未思考到有源汇上下界最大流脑子就寄了，我们先来思考

无源汇有上下界可行流

怎么想到的呢？
仔细思考一下，我们是怎么学会网络最大流的？ 显然是从可行流开始的吧！
所以，我们来看看，在推完该推的流后，接下来要做什么？
不难想到，记录该点的出流与入流之差，然后从点 S 向所有出流为正的（有入流的），从 T 向所有出流为负的（有出流的）连一条流量为差的边，然后跑一次网络最大流，就解决了。
欸，为甚么？
我们先来想一想。
源汇点和其他点的区别是什么？
它们不满足流量守恒嘛！
那么，只要让源汇点满足流量守恒不就行了？
因此，我们就自然想到(这里就不用加句号了吧)。

无源汇有上下界可行流 转化【模板】网络最大流

本来这里有个箭头，但非数学公式不得使用 LaTex，大家将就着看吧
如何让源汇点满足流量守恒呢？
先来回想一下刚学最大流时水流的比喻。 ::::info[想看的自己看] 源点是自来水厂，汇点是你家。
如果自来水厂没水了怎么办？
找人借呗！
但是上一次操作把所有点干进了流量守恒，情势有9分甚至10分的危急，于是，自来水厂把目光放到了
你家。 希望上面那个故事让你深刻理解了无源汇有上下界可行转化成网络最大流的过程
有的同学可能还没明白，那我用书面一点的语言表述一下：
:::: 我们可以通过连接一条边 t→s，容量为 [0,+∞]，这样就能使得 s 流出的流量由 t 提供，t 流入的量由 s 提供，进而达到收支平衡。这样子跑一遍无源汇有上下界可行流，就可以使得到一组可行解了。其中，在 t→s 这条边上流过的流量就是一个可行的方案的答案了。换句话说，在 t→s 这条边流过的流量就是它的反向边（即残量网络的对应边）的流量。

省流：连接一条边 t→s，容量为 [0,+∞]

然后，如果在加入 s 与 t 的情况下它可以跑满，则没有它们，所有出流也一定可以补充一个入流的入流，所以：
:::::::::warning[接下来的内容又长又臭，建议直接查看省流] 无源汇上下界可行流通过构造超级源汇点平衡初始流的不平衡性若新网络中超级源点出边满流则原问题存在满足流量守恒和边约束的可行解这是因为超级源点的出边满流表明所有初始流量不平衡的节点都得到了充分补偿从而保证了网络中每个节点的流入等于流出（流量守恒）同时所有边的流量也严格处于上下界约束范围内。

::::::::: 好长

省流：这是对的

这时，如果有人杠杆原理学的好就是爱抬杠，他肯定会说：就算我们学会了有源汇有上下界可行流，但我们要解决的不是这个，而是
【模板】有源汇上下界最大流
这可是一道高贵的紫题，敢问阁下又该如何应对？
答：直接应对

有源汇上下界最大流 转化 【模板】网络最大流

无箭头原因同上
其实，仔细观察我们跑过一次有源汇有上下界可行流的图。
你会惊奇的发现，哎，我的边剩余流量的取值范围怎么变成 [0,R_i?L _i] 了？
那我的 【模板】网络最大流 不就派上用场了？ 于是，我们只需正常的建立正常源点和正常汇点，跑一遍普通网络最大流就过关了。

想一想你就懂了！
我们只要在跑完可行流之后把超级源汇删掉，那跑出来的不就是最大流了吗？
这时，我们注意到，由于 s 没有入边，而 t 没有出边，因此增广路不会经过 s,t，也就不会导致约束条件失效了！
于是，只要把两次最大流的结果加起来，问题就解决了！

2.代码

:::::::::warning[不要试图贺代码] 因为贺了你也过不去 :::::::::

#include<bits/stdc++.h>
using namespace std;
const int inf=1<<30;
int cnt=1,head[13000],dep[13000],gap[13000];
long long maxflow;
int n,m,s,t;
struct Node{
    int u,v,w;
}node[250000];
inline void addedge(int u,int v,int w){
    node[++cnt].v=v;
    node[cnt].w=w;
    node[cnt].u=head[u];
    head[u]=cnt;
    node[++cnt].v=u;
    node[cnt].liu=0;
    node[cnt].u=head[v];
    head[v]=cnt;
}
void bfs(){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    dep[t]=0;
    gap[0]=1;
    queue<int>q;
    q.push(t);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=node[i].u){
            int v=node[i].v;
            if(dep[v]!=-1)continue;
            q.push(v);
            dep[v]=dep[u]+1;
            gap[dep[v]]++;
        }
    }
    return;
}
int dfs(int u,int flow){
    if(u==t){
        maxflow+=flow;
        return flow;
    }
    int used=0;
    for(int i=head[u];i;i=node[i].u){
        int d=node[i].v;
        if(node[i].w&&dep[d]+1==dep[u]){
            int mi=dfs(d,min(node[i].w,flow-used));
            if(mi){
                node[i].w-=mi;
                node[i^1].w+=mi;
                used+=mi;
            }
            if(used==flow)return used;
        }
    }
    --gap[dep[u]];
    if(gap[dep[u]]==0)dep[s]=n+1;
    dep[u]++;
    gap[dep[u]]++;
    return used; 
}
long long ISAP(){
    maxflow=0;
    bfs();
    while(dep[s]<n)dfs(s,inf);
    return maxflow;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int u,v,w;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)cin>>u>>v>>w,addedge(u,v,w);
    cout<<ISAP();
    return 1;//露出鸡脚
}

3.后记

真正的上下界，是蒟蒻的想象力上限与正解之间的鸿沟
当你觉得紫题=模板题+注释时，该睡了，梦里什么都有
或者，你可以贺一篇题解，题解里啥都有

（完） :::info[警示后入]

不符合推荐标准。原因是：非数学公式（一般英文单词、题目名、算法名、人名等）不应使用 LaTeX。。

不符合推荐标准。原因是：数学公式（运算式、运算符、数学推导、参与运算的常数、作为变量的字母等）应使用 LaTeX；句子末尾应添加句号，且全文使用的句号应一致。。

不符合推荐标准。原因是：不应出现大量无关内容，应只包含题目相关内容，包括但不限于题意简述、题目分析等。