最大流算法
Dinic
割
一个网络的割：存在一个边集，删去集合里的边时，S-T不再连通
最小割
所有割中边权之和最小的
最小割-最大流定理
最小割等于最大流
二分图匹配
(M)为边集(E)的一个子集，如果对于任何一个点，都最多被(M)中一条边覆盖，则成(M)为一个匹配。
最大匹配
使(|M|)最大的一个匹配（可能有多个）
最大匹配求法
源点S向所有X连边，Y向T连边，容量均为1,原始图上边容量均为1，最大流=最大匹配。
二分图最小顶点覆盖
(V')是点集(V)的一个子集，对于任意一条边，至少有一端在(V')内。
最小的一个(V')被称作最小顶点覆盖
最大匹配=最小顶点覆盖
证明：若有一条边未覆盖，则匹配+1，与最大匹配矛盾
二分图最大独立集
(V')是(G)的一个独立集，当且仅当对于任何一条边，它至少有一端不在(V')内
最大独立集大小等于(|V|-)最大匹配
证明：最小割。若(S,x)为割边，则在(V')中删去x。y同理。
有向图最小路径覆盖
用尽可能少的简单路径覆盖整张图。特殊的：一个点也是一条简单路径。
二分图建模：把每个点(x)拆成(x_1,x_2),分别属于X,Y.
对原图一条边，(x,y),链接((x_1,y_2))
易证：最小路径覆盖=(|V|-)最大匹配。
X中未被匹配的点是每条路径的起点
二分图点权最大独立集
最大权独立集=(sum value(x) -)最小权顶点覆盖
最小权覆盖=最大匹配=最小割=最大流(原图的边流量为无穷大)
建图：S向所有X连边，容量为value(x),所有的Y向T连边，容量为value(y) ，原图中的边容量为无穷大
最大权闭合子图
(U)是(G)的一个子图，x属于(U) 当且仅当对于任何一条边(x,y)，y也属于(U),那么(U)是(G)的一个闭合子图
权值和最大的闭合子图称为最大权闭合子图(权值有正有负)
求法：建立源点S,向所有x(value(x)>0)连边，容量为value(x),建立汇点T,所有y(value(y)<0)向T连边，容量为-value(y),对于原图中的边(x,y)，在x,y之间连一条容量为无穷大的边。
最大权闭合子图=(sum_{value(x)>0} value(x) -) 最小割
证明：
若选了一个点x,则他的后继一定会选(最大流)，满足闭合子图。
若一个(S,x)为割边，说明(S,x)满流，则选了x,他的后继付出的代价一定不小于x的权值，即x的贡献小于等于0
有节点容量的最大流
建图：对于每一个点x拆成两个点(x_1,x_2)，对于所有入边，链接(x_1)出边从(x_2)出，(x_1,x_2)之间链接一条容量为节点容量的边
上下界网络流
每条边有流量上界和流量下界
建图：先建新源点S1,新汇点T1,对于一条边(x,y) ，从x到y连一条(c(e)-l(e))的边，从S1向y连一条(l(e))的边，从x向T1连一条(l(e))的边。
建一条从T到S容量为k的边。
存在可行流：从S1出发的所有边都满流。
最小流：二分K,存在可行流，最小的K即为最小流
最大流：先跑可行流。跑完以后，把自己加入的必要弧删去，再恢复源汇，尝试增广S-T
费用流
算法：ZKW费用流
板子
最大流(BZOJ1694)
#include<cstdio>
#include<cstring>
#include<queue>
const int maxn = 1010;
const int maxm = 2e5+10;
const int inf = 0x3f3f3f3f;
int n,k,S,T,wet[maxm],nxt[maxm],to[maxm],hd[maxn],cnt=1,dis[maxn],cur[maxn];
std::queue<int> Q;
inline void add(int u,int v,int w) {
nxt[++cnt]=hd[u];
hd[u]=cnt;
to[cnt]=v;
wet[cnt]=w;
}
inline bool bfs(void) {
for(int i = 0;i<=T;++i) cur[i]=hd[i];
memset(dis,0,sizeof dis);
dis[S]=1;
Q.push(S);
while(!Q.empty()) {
int u = Q.front();
Q.pop();
for(int i = hd[u];i;i=nxt[i]){
int nx = to[i];
if(!dis[nx]&&wet[i]>0) {
dis[nx]=dis[u]+1;
Q.push(nx);
}
}
}
return dis[T]!=0;
}
inline int dfs(int u,int flow) {
if(u==T) return flow;
int tmp = 0;
for(int &i = cur[u];i;i=nxt[i]) {
int nx = to[i];
if(dis[nx]==dis[u]+1&&wet[i]>0) {
int ret = dfs(nx,std::min(flow,wet[i]));
if(ret<0) ret=0;
flow-=ret;
tmp+=ret;
wet[i]-=ret;
wet[i^1]+=ret;
if(flow==0) break;
}
}
return tmp;
}
inline int dinic(void) {
int flow = 0;
while(bfs()) {
flow+=dfs(S,inf);
}
return flow;
}
int main() {
scanf("%d%d",&n,&k);
for(int i = 0;i<k;++i) {
int x,y;
scanf("%d%d",&x,&y);
add(x,n+y,1);
add(n+y,x,0);
}
S = 0;
T = n+n+1;
for(int i = 1;i<=n;++i) {add(S,i,1);add(i,S,0);}
for(int i = n+1;i<=n+n;++i) {add(i,T,1);add(T,i,0);}
printf("%d",dinic());
return 0;
}
费用流
#include<cstdio>
#include<cstring>
#include<queue>
typedef long long ll;
const int maxn = 5050,maxm=1e5+10;
const int inf = 0x3f3f3f3f;
int n,m,S,T,cnt=1,wet[maxm],fee[maxm],hd[maxn],nxt[maxm],to[maxm];
int dis[maxn],cur[maxn];
bool vis[maxn];
std::queue<int> Q;
inline void add(int u,int v,int w,int f) {
nxt[++cnt]=hd[u];
to[cnt]=v;
wet[cnt]=w;
fee[cnt]=f;
hd[u]=cnt;
}
inline bool spfa(void) {
memset(dis , 0x3f3f3f3f , sizeof dis);
memset(vis, 0 , sizeof vis);
for(int i = 1;i<=n;++i) cur[i]=hd[i];
Q.push(S);
dis[S]=0;
while(!Q.empty()) {
int u = Q.front();
Q.pop();
vis[u]=0;
for(int i = hd[u];i;i=nxt[i]) {
int nx = to[i];
if(dis[nx]>dis[u]+fee[i]&&wet[i]) {
dis[nx]=dis[u]+fee[i];
if(!vis[nx]) {
Q.push(nx);
vis[nx]=1;
}
}
}
}
return dis[T]!=dis[0];
}
inline int dfs(int u,int c,int &flow ,ll &ans) {
vis[u]=1;
if(u==T) {
flow+=c;
ans+=dis[u]*c;
return c;
}
int tmp = 0;
for(int &i = cur[u];i;i=nxt[i]) {
int nx = to[i];
if(!vis[nx]&&wet[i]>0&&dis[nx]==dis[u]+fee[i]) {
int t = dfs(nx,std::min(c,wet[i]),flow,ans);
wet[i]-=t;
wet[i^1]+=t;
tmp+=t;
c-=t;
}
}
return tmp;
}
inline void dinic(void) {
int flow = 0;
ll ans = 0;
while(spfa()) {
vis[T]=1;
while(vis[T]) {
vis[T]=0;
dfs(S,inf,flow,ans);
}
}
printf("%d %lld
",flow,ans);
return;
}
int main() {
scanf("%d%d%d%d",&n,&m,&S,&T);
for(int i = 0;i<m;++i) {
int u,v,w,f;
scanf("%d%d%d%d",&u,&v,&w,&f);
add(u,v,w,f);
add(v,u,0,-f);
}
dinic();
return 0;
}