网络流
xzyxzy
2018-02-03 21:47:55
#**网络流**
Tags：算法
##更好阅读体验：https://www.zybuluo.com/xzyxzy/note/992041
----------
##**一、基本内容**
###**>inic基本内容**
SYC:http://www.cnblogs.com/SYCstudio/p/7260613.html
**朴素DFS->局限性->反悔边->低效->分层图->当前弧优化->Dinic！**
###**>费用流基本内容**
本宝宝自己写：
1.在每一条边上有单位流量的费用，你要保证流量最大的前提，费用最小
2.算法由最朴素的算法该进，便是在BFS求增广路的时候以费用为关键字跑SPFA
3.看代码
###**>上下界网络流**
留坑
###**>最长反链覆盖**
留坑
----------
##**二、题目**
###**1、练基础**
P3376 【模板】网络最大流 https://www.luogu.org/problemnew/show/3376
P3381 【模板】最小费用最大流 https://www.luogu.org/problemnew/show/3381
H1369 网络流一 http://hihocoder.com/problemset/problem/1369
H1378 网络流二 http://hihocoder.com/problemset/problem/1378
H1393 网络流三 http://hihocoder.com/problemset/problem/1393
H1394 网络流四 http://hihocoder.com/problemset/problem/1394
H1398 网络流五 http://hihocoder.com/problemset/problem/1398
P1231 教辅的组成 https://www.luogu.org/problemnew/show/P1231
P1343 地震逃生 https://www.luogu.org/problemnew/show/1343
P2153 [SDOI2009]晨跑 https://www.luogu.org/problemnew/show/2153
P3440 [POI2006]SZK-Schools https://www.luogu.org/problemnew/show/P3440
###**2、刷提高**
P2472 [SCOI2007]蜥蜴 https://www.luogu.org/problemnew/show/2472
P2944 [USACO]地震损失2 https://www.luogu.org/problemnew/show/2944
P1345 [USACO]奶牛的电信 https://www.luogu.org/problemnew/show/1345
P2711 小行星 https://www.luogu.org/problemnew/show/P2711
P2469 [SDOI2010]星际竞速 https://www.luogu.org/problemnew/show/2469
P2057 善意的投票 https://www.luogu.org/problemnew/show/2057
P3410 拍照 https://www.luogu.org/problemnew/show/3410
###**[3、网络流24题][1]**
####已完成
P2763 试题库问题 https://www.luogu.org/problemnew/show/2763
P3254 圆桌问题 https://www.luogu.org/problemnew/show/3254
P4013 数字梯形问题 https://www.luogu.org/problemnew/show/4013
P4016 负载平衡问题 https://www.luogu.org/problemnew/show/4016
P2756 飞行员配对方案问题 https://daniu.luogu.org/problemnew/show/2756
P3355 骑士共存问题 https://www.luogu.org/problemnew/show/3355
P2774 方格取数问题 https://www.luogu.org/problemnew/show/2774
P2765 魔术球问题 https://www.luogu.org/problemnew/show/2765
P2764 最小路径覆盖问题 https://www.luogu.org/problemnew/show/2764
P4014 分配问题 https://www.luogu.org/problemnew/show/4014
P2762 太空飞行计划问题 https://www.luogu.org/problemnew/show/2762
P2766 最长不下降子序列问题 https://www.luogu.org/problemnew/show/2766
P1251 餐巾计划问题 https://www.luogu.org/problemnew/show/1251
####未完成/不可做
###**4、考试题**
2018.1.3 团圆(费用流)
2018.1.5 变量(最小割)
----------
##**三、做题经验**
###**Part 1 易打错**
####**1、当前弧优化的循环重点别弄错**
```cpp
while(BFS())
{
for(int i=1;i<=cnt;i++)cur[i]=head[i];
while(int tmp=DFS(S,INF))ans+=tmp;
}
```
```cpp
for(int i=1;i<=点数;i++)cur[i]=head[i];
```
题目来源：试题库问题P2763
####**2、源点的deep一定要是1 不然跑不出来**
```cpp
deep[S]=0;Q.push(S);
```
```cpp
deep[S]=1;Q.push(S);
```
####**3、跑最大费用最大流时，dis初值为-inf**
```cpp
for(int i=0;i<=T;i++)dis[i]=-10000;
```
```cpp
for(int i=0;i<=T;i++)dis[i]=-1;
```
因为有-cost的边所以-1会出错
题目来源：分配问题P4014
####**4、最大流，费用流都可以跑环**
最大流分层图可以跑环，费用流SPFA也可以
----------
###**Part 2 技巧**
####**1、拆点连边技巧**
蜥蜴：https://www.luogu.org/problemnew/show/P2472
为了限制一个点的流量，将它拆成两个点并连边
连**有向边**的时候一条边为w，cost，反过来为0，-cost
连**无向边**正反都是w
####**2、记录匹配方案**
满流的边便是匹配上了
P2763 试题库问题 https://www.zybuluo.com/mdeditor#980353
P2756 飞行员配对方案问题 https://daniu.luogu.org/problemnew/show/2756
####**3、某边改变时**
并不需要重新建图
A、判断某条边(u->v)属不属于割集，那么在残余网络中u到达不了v
B、对于一条边扩容，那么在残余网络上找增广路就好了
C、减少一条边的容量，在残余网络中找是否有该容量的路，再分情况更新
例：团圆(考试题)，看某一条边是不是必须要的，重新跑SPFA即可
####**4、最小割问题**
> **最小割:**
割是网络中定点的一个划分，它把网络中的所有顶点划分成两个顶点集合S和T，其中源点s∈S,汇点t∈T。记为CUT(S,T)，满足条件的从S到T的最小的割
[百度][2]告诉我们，最小割等于最大流
但是求的是割点的时候呢，哈哈，死掉了吧————[奶牛的电信][3]
这些最小割真的哦心【[你猜呀！][4]】【[你阅读了吗？][5]】【[死掉了吧～][6]】
####**5、有关术语**
参考博客：https://www.cnblogs.com/jianglangcaijin/p/6035945.html
>**最小顶点覆盖**
能覆盖所有的边的最少顶点数(或是最小点权和)
计算方法：最小顶点覆盖=最大匹配数
>**最大独立集**
两两互不相邻的点组成的集合的最大点数(或是最大点权和)
计算方法：最大独立集=点总数-最小顶点覆盖
**例题剖析——[方格取数问题][7]**
和小行星有点类似，小行星是x,y,z要消掉一个使得消掉行星，便是S-x-y-z-T的流不存在，即求最小割，转化为最大流；此题把方格化为黑白点，便不存在 S->黑点->白点->T的流，顺次进行连边求最小割即最大流即可，注意**边权**
又用转化思想，化为黑白点后可以看做二分图，便成了最大独立集，为总点数-最小顶点覆盖(最大匹配/最小割)
>**最小路径覆盖**
能覆盖所有点的最少边数(边权之和)
友链：http://blog.csdn.net/tramp_1/article/details/52742572
计算方法：二分图最小路径覆盖=一侧点数-最大匹配数
运用：常用来解决不重不漏经过图中所有点的问题，一般化u为u和u'，对于边(u，v),link(u,v')，最大匹配数在网络流中就是最小割/最大流，[看看这题][8]
理解：最差每个点就是一条路径，每连一条边(一个匹配)就少一条路径，n-匹配数
ps：自己习惯于跑费用流，把点拆成上下两层后这样搞：
```link(S,u,1,0); link(S,u',1,1); link(u',T,1,0); link(u,v',1,0);```
>**最大权闭合子图**
给定一个有向图，从中选择一些点组成一个点集V。对于V中任意一个点，其后续节点都仍然在V中
计算方法：最大权=所有正点和-最小割
或者说是最大收益问题【[模板1][9]】【[模板2][10]】【[模板3][11]】
----------
###**Part 3 转化思想**
####**1、最小割思想**
很多情况下，对于网络中的每个点存在有两种状态，选或不选同意或反对等等
就将它们分成两个集合S,T表示两种对立的状态，而且点与点之间也有相互的关系
改变某点的状态需要一定代价，并因此连边。
**举个例子**
[最大权闭合子图][12]中，假设所有实验都选，获得收益，那么最终答案是总收益-总损失，损失表示买一个器材的代价或者放弃一个实验的损失
每个实验和器材存在有选或不选的关系，假设选为S，不选为T，那么把实验与S连边，器材与T连边后，损失成了图的最小割，最小割的割集一定由与S/T相连的边组成（中间为正无穷）。**当实验不选的时候，相当于割掉其与S的边，造成其边流量的损失，计算到最小割里；当器材要选的时候，相当于割掉其与T的边，造成其边流量的代价买器材，计算到最小割里。**
**边容量**
一般呢，哪两个点不可割就连inf，x连到S会产生w贡献那么连x到T，容量为w
####**2、上升序列思想**
主要是[这题][13]，求某一长度的上升序列的个数，那么转化成最大流，DP求出转移后，每个点只能向该点转移到的点连边（并不是比它大就能连边），所以一条流经过的路径数就是上升序列的长度。
----------
##**最大流模板**
```cpp
//https://www.luogu.org/problemnew/show/3376
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=10010;
const int MAXM=100010;
int N,M,S,T,ans,deep[MAXN];
int head[MAXN],cnt=1,cur[MAXN];
struct edge{int next,to,w;}a[MAXM<<1];
void link(int x,int y,int w){a[++cnt]=(edge){head[x],y,w};head[x]=cnt;}
int read();
queue<int>Q;
int BFS()//分好层
{
memset(deep,0,sizeof(deep));
deep[S]=1;Q.push(S);
while(!Q.empty())
{
int now=Q.front();Q.pop();
for(int i=head[now];i!=-1;i=a[i].next)
if(!deep[a[i].to]&&a[i].w)
{deep[a[i].to]=deep[now]+1;Q.push(a[i].to);}
}//给每个深度编号
return deep[T];
}
int DFS(int x,int flow)//在该层寻找所有增广路
{
if(x==T)return flow;//返回最大流
for(int &i=cur[x];i!=-1;i=a[i].next)
//&这个符号,表示i去到cur[x]的地址,那么首先i=cur[x]然后随着i的改变cur[x]跟着改变
{
if(!a[i].w||deep[a[i].to]!=deep[x]+1)continue;//要求有流且在下一层
int tmp=DFS(a[i].to,min(a[i].w,flow));
if(tmp){a[i].w-=tmp;a[i^1].w+=tmp;return tmp;}
//记得加反悔边,return tmp表示找到一条流就退出，是单路增广
}
return 0;
}
int main()
{
//Part 1 输入建图
N=read();M=read();
S=read();T=read();
memset(head,-1,sizeof(head));
for(int i=1;i<=M;i++)
{
int x=read(),y=read(),w=read();
link(x,y,w);link(y,x,0);//建边的时候要建立反悔边
}
//Part 2 逐层找增广路
while(BFS())//走的到终点即存在增广路
{
for(int i=1;i<=N;i++)cur[i]=head[i];//当前弧优化
while(int tmp=DFS(S,10000000))ans+=tmp;//加上增广的最大流
}
printf("%d\n",ans);
return 0;
}
int read()
{
char ch=getchar();
int h=0;
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
return h;
}
/*
网络流Dinic
1.流程:
A.输边建图(记得加上反悔边)
B.分层跑增广路
C.重复B直到从源点走不到汇点
2.理解:
A.反悔边:详见SYC博客http://www.cnblogs.com/SYCstudio/p/7260613.html
B.如何说明分层跑是对的或者说如何跑的:
a.每一层跑完后,S一定会到不了T
b.那么在deep[T]步走不到T,那么要走到T,必须加上之前连接同一层的两个点,deep[T]至少加1
C.复杂度:
分层M,至少分N次,DFS一次是N,然后一次至少有一条边流满即剩余流量为0,视为删掉一条边
然后也许有M次所以复杂度为O(N*N*M)
然而实际上复杂度要小的多,这道题10000*10000*100000可是在0.05ms内跑过的
D.当前弧优化:
每次分好层之后,对于点P,有流进P的边和从P流出的边
如果这条边流出满了,下次就不要搜这条边,用cur记录(没流满就return了)
*/
```
##**费用流模板**
```cpp
//https://www.luogu.org/problemnew/show/P3381
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
int read()
{
char ch=getchar();
int h=0;
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
return h;
}
const int MAXN=5001;
int N,M,S,T,head[MAXN],cnt=1,anssum=0,anscost=0;
struct edge{int next,to,w,cost;}a[MAXN*20];
void link(int x,int y,int w,int cost)
{
a[++cnt]=(edge){head[x],y,w,cost};head[x]=cnt;
a[++cnt]=(edge){head[y],x,0,-cost};head[y]=cnt;
}
queue<int>Q;
int dis[MAXN],e[MAXN],pe[MAXN],px[MAXN];
//pe[i]表示到达i点的那一条边的编号
//px[i]表示到达i点的前驱节点编号
bool SPFA()
{
memset(dis,63,sizeof(dis));
dis[S]=0;Q.push(S);
while(!Q.empty())
{
int x=Q.front();
for(int i=head[x];i!=-1;i=a[i].next)
{
int R=a[i].to;
if(!a[i].w||dis[R]<=dis[x]+a[i].cost)continue;
dis[R]=dis[x]+a[i].cost;
pe[R]=i;px[R]=x;
if(!e[R]){e[R]=1;Q.push(R);}
}
e[x]=0;Q.pop();
}
return dis[T]<dis[0];
//当不存在增广路时dis[T]=dis[0]
}
int main()
{
//init
N=read();M=read();S=read();T=read();
memset(head,-1,sizeof(head));
for(int i=1;i<=M;i++)
{
int x=read(),y=read(),w=read(),cost=read();
link(x,y,w,cost);
}
//work
while(SPFA())//算出增广路上的流
{
int sum=1e9;
for(int i=T;i!=S;i=px[i])
sum=min(sum,a[pe[i]].w);
anscost+=dis[T]*sum;//记录最小费用-流量×每条边单位流量费用之和
anssum+=sum;//记录最大流
for(int i=T;i!=S;i=px[i])
a[pe[i]].w-=sum,a[pe[i]^1].w+=sum;//逐边减
}
printf("%d %d\n",anssum,anscost);
return 0;
}
```
参考文献：
####**SYC：http://www.cnblogs.com/SYCstudio/p/7260613.html**
ZSY：https://www.luogu.org/blog/zhoushuyu/wang-lao-liu-zong-jie
小想法：
如果以后要出题，试着来一个费用流但是不是单位流量费用而是凡有流就有费用
[1]: http://www.cnblogs.com/zhoushuyu/p/8168712.html
[2]: https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E6%B5%81%E6%9C%80%E5%B0%8F%E5%89%B2%E5%AE%9A%E7%90%86/3851799?fr=aladdin
[3]: https://www.luogu.org/problemnew/show/P1345
[4]: https://www.luogu.org/problemnew/show/2944
[5]: https://www.luogu.org/problemnew/show/P2711
[6]: https://www.luogu.org/problemnew/show/2057
[7]: https://www.luogu.org/problemnew/show/2774
[8]: https://www.luogu.org/problemnew/solution/P2469
[9]: http://hihocoder.com/problemset/problem/1398
[10]: https://www.luogu.org/problemnew/show/P3410
[11]: https://www.luogu.org/problemnew/show/2762
[12]: https://www.luogu.org/problemnew/show/2762
[13]: https://www.luogu.org/problemnew/show/2766