前言：
网络流就像自来水厂到你家的水管，自来水厂(源点S)源源不断的提供水，水通过不同水管汇集于你家(设自来水厂的水全到你家，汇点T)。自来水厂到你家的水管网是一个复杂的有向图，每一节水管都有一个最大承载流量(容量)。自来水厂不放水，你家就没水了。但是就算自来水厂拼命地往管网里面注水，你家收到的水流量也是上限，毕竟每根水管承载量有限。这就是一个有向图，所有的水都从一个点流出（水厂），最后全部汇聚到一个点（你家）。
网络(流网络)是指一个有向联通图，由一个点集和一个边集构成 G=(V,E)。
ps:不考虑反向边，如果有反向边，通过加点变成没有反向边的图。
\(\;\;\;\) 如果一条边不存在，则定义这条边的容量是0。
对于一个网络流图 G=(V,E)，每条边（u,v）上给定一个实数 f(u,v)，f(u,v) 为 边(u,v) 上的流量。
对于任何一条有向边(u,v)，f(u,v)=-f(v,u)
一个可行流f需满足两个条件:
流量守恒：$$∀x\in ( V − { S,T} )，\sum\limits_{∀(v,x)∈E}f(v,x)=\sum\limits_{∀(x,v)∈E}f(x,v)$$
除源点和汇点外，流入其余每一个点的流量和等于流出这个点的流量和，不存储流量。
容量限制 0 \(\leq\) f(u,v) \(\leq\) c(u,v)
我们永远赚不到自己认知以外的钱，水管也永远装不下比自己容量还大的水
|f| 表示可行流的流量值，定义为从源点流出的流量或汇点流入的流量.
|f| =\(\sum\limits_{(s,v)ϵE}\)f(s,v) − \(\sum\limits_{(v,s)ϵE}\)f(v,s)
和流网络的关系：一个流网络中有很多个可行流，G\(\begin{cases} f_1\\f_2\\f_3\\\vdots\end{cases}\)
流网络里的每一个可行流f都有自己的残留网络\(G_f\)，对于不同的可行流，残留网络不同。
残留网络同样也是由一个点集和一个边集构成,\(G_f\)=(\(V_f\),\(E_f\))
而残留网络中，边的容量c'(u,v)是原网络的残留容量
c'(u,v)=\(\begin{cases}c(u,v)-f(u,v)\;\; (u,v)\in E ,表示还有多少流量可以用，容量减去流量\\f(v,u) \qquad \;\,\qquad (v,u)\in E ,表示可以退回去多少流量\end{cases}\)
流量计算：|f+f'|=|f|+|f'|
流量相加指的是每条边对应相加：残留网络和原网络边的方向相同，累加；相反，相当于退回的流量，减去；
反向边是一个很牛逼的反悔机制，可以把前面流的流量退回去。这样，就能多去考虑被之前的通路阻断的情况，不会漏解。换句话说，反向边的存在让我们可以在所有的情况里选取最符合我们所需的情况。
f'+f也是原网络G的另外一个可行流。
1.流量守恒证明
\(\quad\;\;\because\) f和f'都满足流量守恒
\(\quad\;\;\therefore ∀x\in ( V − \{S,T\} )\sum\limits_{∀(v,x)∈E}f(v,x)+\sum\limits_{∀(v,x)∈E}f'(v,x)=\sum\limits_{∀(x,v)∈E}f(x,v)+\sum\limits_{∀(x,v)∈E}f'(x,v)\)
\(\quad\;\;\therefore\) f+f'满足流量守恒
2.容量限制证明
\(\quad\;\;\because\) 0 \(\leq\) f'(u,v) \(\leq\) c'(u,v)=c(u,v)-f(u,v)
\(\quad\;\;\therefore\) 0 \(\leq\) f'(u,v) \(\leq\) c'(u,v)=c(u,v)-f(u,v)
\(\quad\;\;\therefore\) 0 \(\leq\) f'(u,v) + f(u,v) \(\leq\) c(u,v) 满足正向边容量限制
\(\quad\;\;\because\) 0 \(\leq\) f'(u,v) \(\leq\) c'(u,v)=f(v,u) \(\leq\) c(v,u)
\(\quad\;\;\therefore\) 0 \(\leq\) f(v,u) - f'(u,v) \(\leq\) c(u,v)
\(\quad\;\;\therefore\) 0 \(\leq\) f(v,u) + f'(v,u) \(\leq\) c(u,v) 满足反向边容量限制
残留网络里，从源点沿着流量 > 0的边能够走到汇点，这样的路径为增广路径。
对于当前流网络里的可行流来说，残留网络里无增广路径，则该可行流为最大流。
对于一个流网络来说，有很多可行流最大流是最大可行流。
基于FF方法的一种算法
由最大流的定义得知，当残留网络里，不存在增广路时，当前可行流为最大流，那么EK算法就是把增广路一条一条的找到，那么不断地消除这一条条增广路，从而求得最大流。对增广路对应的原图里面的路径增流，就可以消除这条增广路。
我们不断的重复上面两个操作，直到找不到增广路为止，则没有一条路径可以给汇点增加流量。此时，汇点汇集的流量为最大流。
那么如果一条更优的路径被前面消除的一条路截断了怎么办呢？
这个时候，反向边的反悔机制，就起到了很牛逼的作用，我直接反悔，把这个之前通过增流消除的增广路进行退流，把之前增加的流量退回来，对当前更优的增广路进行消除，就ok了
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1010,M=20010,inf=1e8;
int e[M],ne[M],f[M];
int q[N],d[N],h[N],pre[N],idx;
int m,n,S,T;
bool st[N];
void add(int a,int b,int c)
{
e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
int tt=0,hh=0;
memset(st,0,sizeof st);
q[0]=S,st[S]=true,d[S]=inf;
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int ver=e[i];
if(!st[ver]&&f[i])
{
st[ver]=true;
d[ver]=min(f[i],d[t]);
pre[ver]=i;
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
inline int EK()
{
int ans=0;
while(bfs())
{
ans+=d[T];
for(int i=T;i!=S;i=e[pre[i]^1])
{
f[pre[i]]-=d[T],f[pre[i]^1]+=d[T];
}
}
return ans;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&S,&T);
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
printf("%d\n",EK());
return 0;
}
blablablabla...
对EK算法的一种优化
在EK的基础上建立分层图，
每次一层层跑最短路 相比于EK算法 减少了很多不必要的循环 可以更高效的消除增广路
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=10100,M=200100,inf=1e8;
int e[M],ne[M],f[M];
int q[N],d[N],h[N],cur[N],idx;
int m,n,S,T;
void add(int a,int b,int c)
{
e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
int tt=0,hh=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0,cur[S]=h[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int ver=e[i];
if(d[ver]==-1&&f[i])
{
d[ver]=d[t]+1;
cur[ver]=h[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
inline int find(int u,int limits)
{
if(u==T) return limits;
int flow=0;
for(int i=cur[u];~i&&flow<limits;i=ne[i])
{
int ver=e[i];
cur[u]=i;
if(d[ver]==d[u]+1&&f[i])
{
int t=find(ver,min(f[i],limits-flow));
if(!t) d[ver]=-1;
f[i]-=t;
f[i^1]+=t;
flow+=t;
}
}
return flow;
}
inline int Dinic()
{
int ans=0,flow;
while(bfs())
{
while(flow=find(S,inf)) ans+=flow;
}
return ans;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&S,&T);
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
printf("%d\n",Dinic());
return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1010,M=30010,inf=1e8;
int e[M],ne[M],f[M],l[M];
int q[N],d[N],h[N],cur[N],idx,A[N];
int m,n,S,T;
void add(int a,int b,int c,int d)
{
e[idx]=b,f[idx]=d-c,l[idx]=c,ne[idx]=h[a],h[a]=idx++;
e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx++;
}
bool bfs()
{
int tt=0,hh=0;
memset(d,-1,sizeof d);
q[0]=S,d[S]=0,cur[S]=h[S];
while(hh<=tt)
{
int t=q[hh++];
for(int i=h[t];~i;i=ne[i])
{
int ver=e[i];
if(d[ver]==-1&&f[i])
{
d[ver]=d[t]+1;
cur[ver]=h[ver];
if(ver==T) return true;
q[++tt]=ver;
}
}
}
return false;
}
inline int find(int u,int limit)
{
if(u==T) return limit;
int flow=0;
for(int i=cur[u];~i&&flow<limit;i=ne[i])
{
int ver=e[i];
cur[u]=i;
if(d[ver]==d[u]+1&&f[i])
{
int t=find(ver,min(f[i],limit-flow));
if(!t) d[ver]=-1;
f[i]-=t;
f[i^1]+=t;
flow+=t;
}
}
return flow;
}
inline int Dinic()
{
int ans=0,flow;
while(bfs())
{
while(flow=find(S,inf)) ans+=flow;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
S=0,T=n+1;
memset(h,-1,sizeof h);
for(int i=1;i<=m;i++)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
add(a,b,c,d);
A[a]-=c,A[b]+=c;
}
int tot=0;
for(int i=1;i<=n;i++)
{
if(A[i]>0)
{
add(S,i,0,A[i]);
tot+=A[i];
}
else if(A[i]<0)
{
add(i,T,0,-A[i]);
}
}
if(Dinic()!=tot) puts("NO");
else
{
puts("YES");
for(int i=0;i<2*m;i+=2)
{
printf("%d\n",f[i^1]+l[i]);
}
}
return 0;
}
有时间再写..
我想在Ruby中创建一个用于开发目的的极其简单的Web服务器(不，不想使用现成的解决方案)。代码如下:#!/usr/bin/rubyrequire'socket'server=TCPServer.new('127.0.0.1',8080)whileconnection=server.acceptheaders=[]length=0whileline=connection.getsheaders想法是从命令行运行这个脚本，提供另一个脚本，它将在其标准输入上获取请求，并在其标准输出上返回完整的响应。到目前为止一切顺利，但事实证明这真的很脆弱，因为它在第二个请求上中断并出现错误:/usr/b
网络编程套接字网络编程基础知识理解源`IP`地址和目的`IP`地址理解源MAC地址和目的MAC地址认识端口号理解端口号和进程ID理解源端口号和目的端口号认识`TCP`协议认识`UDP`协议网络字节序socket编程接口`sockaddr``UDP`网络程序服务器端代码逻辑：需要用到的接口服务器端代码`udp`客户端代码逻辑`udp`客户端代码`TCP`网络程序服务器代码逻辑多个版本服务器单进程版本多进程版本多线程版本线程池版本服务器端代码客户端代码逻辑客户端代码TCP协议通讯流程TCP协议的客户端/服务器程序流程三次握手（建立连接）数据传输四次挥手（断开连接）TCP和UDP对比网络编程基础知识
目录前言滤波电路科普主要分类实际情况单位的概念常用评价参数函数型滤波器简单分析滤波电路构成低通滤波器RC低通滤波器RL低通滤波器高通滤波器RC高通滤波器RL高通滤波器部分摘自《LC滤波器设计与制作》，侵权删。前言最近需要学习放大电路和滤波电路，但是由于只在之前做音乐频谱分析仪的时候简单了解过一点点运放，所以也是相当从零开始学习了。滤波电路科普主要分类滤波器：主要是从不同频率的成分中提取出特定频率的信号。有源滤波器：由RC元件与运算放大器组成的滤波器。可滤除某一次或多次谐波，最普通易于采用的无源滤波器结构是将电感与电容串联，可对主要次谐波（3、5、7）构成低阻抗旁路。无源滤波器：无源滤波器，又称
最近在学习CAN，记录一下，也供大家参考交流。推荐几个我觉得很好的CAN学习，本文也是在看了他们的好文之后做的笔记首先是瑞萨的CAN入门，真的通透；秀！靠这篇我竟然2天理解了CAN协议！实战STM32F4CAN！原文链接：https://blog.csdn.net/XiaoXiaoPengBo/article/details/116206252CAN详解（小白教程）原文链接：https://blog.csdn.net/xwwwj/article/details/105372234一篇易懂的CAN通讯协议指南1一篇易懂的CAN通讯协议指南1-知乎(zhihu.com)视频推荐CAN总线个人知识总
深度学习部署：Windows安装pycocotools报错解决方法1.pycocotools库的简介2.pycocotools安装的坑3.解决办法更多Ai资讯：公主号AiCharm本系列是作者在跑一些深度学习实例时，遇到的各种各样的问题及解决办法，希望能够帮助到大家。ERROR:Commanderroredoutwithexitstatus1:'D:\Anaconda3\python.exe'-u-c'importsys,setuptools,tokenize;sys.argv[0]='"'"'C:\\Users\\46653\\AppData\\Local\\Temp\\pip-instal
我完全不是程序员，正在学习使用Ruby和Rails框架进行编程。我目前正在使用Ruby1.8.7和Rails3.0.3，但我想知道我是否应该升级到Ruby1.9，因为我真的没有任何升级的“遗留”成本。缺点是什么？我是否会遇到与普通gem的兼容性问题，或者甚至其他我不太了解甚至无法预料的问题？ 最佳答案 你应该升级。不要坚持从1.8.7开始。如果您发现不支持1.9.2的gem，请避免使用它们(因为它们很可能不被维护)。如果您对gem是否兼容1.9.2有任何疑问，您可以在以下位置查看:http://www.railsplugins.or
如何学习ruby的正则表达式？(对于假人) 最佳答案 http://www.rubular.com/在Ruby中使用正则表达式时是一个很棒的工具，因为它可以立即将结果可视化。 关于ruby-我如何学习ruby的正则表达式？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/1881231/
是否可以在不实际下载文件的情况下检查文件是否存在？我有这么大的(~40mb)文件，例如:http://mirrors.sohu.com/mysql/MySQL-6.0/MySQL-6.0.11-0.glibc23.src.rpm这与ruby不严格相关，但如果发件人可以设置内容长度就好了。RestClient.get"http://mirrors.sohu.com/mysql/MySQL-6.0/MySQL-6.0.11-0.glibc23.src.rpm",headers:{"Content-Length"=>100} 最佳答案
我在这方面尝试了很多URL，在我遇到这个特定的之前，它们似乎都很好:require'rubygems'require'nokogiri'require'open-uri'doc=Nokogiri::HTML(open("http://www.moxyst.com/fashion/men-clothing/underwear.html"))putsdoc这是结果:/Users/macbookair/.rvm/rubies/ruby-2.0.0-p481/lib/ruby/2.0.0/open-uri.rb:353:in`open_http':404NotFound(OpenURI::HT
深度学习12.CNN经典网络VGG16一、简介1.VGG来源2.VGG分类3.不同模型的参数数量4.3x3卷积核的好处5.关于学习率调度6.批归一化二、VGG16层分析1.层划分2.参数展开过程图解3.参数传递示例4.VGG16各层参数数量三、代码分析1.VGG16模型定义2.训练3.测试一、简介1.VGG来源VGG（VisualGeometryGroup）是一个视觉几何组在2014年提出的深度卷积神经网络架构。VGG在2014年ImageNet图像分类竞赛亚军，定位竞赛冠军；VGG网络采用连续的小卷积核（3x3）和池化层构建深度神经网络，网络深度可以达到16层或19层，其中VGG16和VGG