本文中 N为点数，M为边数；
EK: (brute_force) ；
每次bfs暴力找到一条增广路，更新流量，代码如下 ：
时间复杂度：O(NM²)；
#include<bits/stdc++.h>
using namespace std; struct node{
int next,to,len;
}edge[]; int val[],head[],vis[],from[];
int n,m,s,t,ans,inf=,cnt=; inline void add_edge(int u,int v,int len){
edge[++cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].len=len;
head[u]=cnt;
} inline bool bfs(){
queue <int> q;
memset(vis,,sizeof(vis));
val[s]=inf;
q.push(s);vis[s]=;
while(q.size()){
int u=q.front(); q.pop();
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if(vis[v]||!edge[i].len)continue;
vis[v]=; q.push(v);
from[v]=i;
val[v]=min(val[u],edge[i].len);
if(v==t)return true;
}
}
return false;
} inline void update(){
int u=t;
while(u!=s){
int p=from[u];
edge[p].len-=val[t];
edge[p^].len+=val[t];
u=edge[p^].to;
}
ans+=val[t];
} int main(){
int x,y,z;
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i=;i<=m;i++){
scanf("%d %d %d",&x,&y,&z);
add_edge(x,y,z);
add_edge(y,x,);
}
while(bfs())update();
printf("%d\n",ans);
return ;
}
Dinic: 显然，EK算法每次只bfs找到一条增广路径是非常睿智低效的，Dinic算法就是通过dfs 每次找到一张增广网，从而使增广速度加快；
p.s. 当前弧优化：在dfs进行增广时，有些边已经对此次的增广做出了全部的贡献（换言之，他在当前的残量网络中已经没有贡献了），所以就不必再考虑它；
代码如下：
时间复杂度：O(Dinic(N, M)) O(N*M½) ~ O(M*N²)；
//15owzLy1
//Dinic.cpp
//2018 10 10 11:51:55
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define lson tl, mid, rt<<1
#define rson mid+1, tr, rt<<1|1
#define pb(__) push_back(__)
#define fr() front()
#define bg() begin()
#define it iterator
#define INF 2100000000
typedef long long ll;
typedef double db; const int N = , M = ; //edge begin
struct node {
int next, to, len;
}edge[M<<];
int head[N], cnt=;
//edge end
int n, m, s, t; template<typename T>inline void read(T &_) {
_=;bool __=;char ___=getchar();
while(___<''||___>''){__|=(___=='-');___=getchar();}
while(___>=''&&___<=''){_=(_<<)+(_<<)+(___^);___=getchar();}
_=__?-_:_;
} template<class T>inline void get_max(T &_, T __) { _=_>__?_:__; }
template<class T>inline void get_min(T &_, T __) { _=_<__?_:__; }
template<class T>inline void Swap(T &_, T &__) { T ___=_;_=__;__=___; }
template<class T>inline T abs(T _) { return _>?_:-_; } inline void jb(int u, int v, int w) {
edge[++cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].len=w;
head[u]=cnt;
} namespace Dinic {
int l, r, q[N], cur[N], dep[N], Max_flow;
inline bool bfs() {
memset(dep, , sizeof(dep));
memcpy(cur, head, sizeof(head));
l=r=; q[++r]=s; dep[s]=;
while(l<r) {
int u=q[++l];
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].to, w=edge[i].len;
if(dep[v]==&&w) dep[v]=dep[u]+, q[++r]=v;
}
}
if(dep[t]) return true;
else return false;
}
int dfs(int u, int min) {
if(min==||u==t) return min;
int flow=, f;
for(int &i=cur[u];i;i=edge[i].next) {
int v=edge[i].to, w=edge[i].len;
if(dep[v]==dep[u]+&&(f=dfs(v, std::min(min, w)))) {
flow+=f; min-=f;
edge[i].len-=f;
edge[i^].len+=f;
}
}
return flow;
}
inline void Dinic() {
int flow;
while(bfs())
while(flow=dfs(s, INF)) Max_flow+=flow;
printf("%d\n", Max_flow);
}
} int main() {
#ifndef ONLINE_JUDGE
freopen("Dinic.in","r",stdin);
freopen("Dinic.out","w",stdout);
#endif
int x, y, z;
read(n), read(m), read(s), read(t);
for(int i=;i<=m;i++) {
read(x), read(y), read(z);
jb(x, y, z), jb(y, x, );
}
Dinic::Dinic();
return ;
}
二分图：顾名思义，就是可以分成两个部分的图（把点分成两边，同一侧的点只能向另一侧的点连边）；
二分图最大匹配：在边中选一个子集，使得每个点最多与该边集中的一个点相连，边数最多的子集即最大匹配；
如何求？？？
1.匈牙利算法(Hungarian method) : (brute_force) ———— 看代码
将点分为两部分（左右两边）；(u在左边，v在右边)
mat[v]=u表示当前与v匹配的点为u;
每次dfs即寻求增广路；
//15owzLy1
//Hungary.cpp
//2018 10 10 17:04:04
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define lson tl, mid, rt<<1
#define rson mid+1, tr, rt<<1|1
#define pb(__) push_back(__)
#define fr() front()
#define bg() begin()
#define it iterator
#define INF 2100000000
typedef long long ll;
typedef double db; const int N = , M = ;
//edge bg;
struct node {
int next, to;
}edge[M*N];
int head[N], cnt=;
//edge end;
int mat[N], n, m, e;
bool vis[N]; template<typename T>inline void read(T &_) {
_=;bool __=;char ___=getchar();
while(___<''||___>''){__|=(___=='-');___=getchar();}
while(___>=''&&___<=''){_=(_<<)+(_<<)+(___^);___=getchar();}
_=__?-_:_;
} template<class T>inline void get_max(T &_, T __) { _=_>__?_:__; }
template<class T>inline void get_min(T &_, T __) { _=_<__?_:__; }
template<class T>inline void Swap(T &_, T &__) { T ___=_;_=__;__=___; }
template<class T>inline T abs(T _) { return _>?_:-_; } inline void jb(int u, int v) {
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
} bool dfs(int u) {
vis[u]=true;
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].to;
if(vis[mat[v]]) continue;
if(mat[v]==||dfs(mat[v])) {
mat[v]=u; return true;
}
}
return false;
} inline int Hungary() {
int res=;
for(int i=;i<=n;i++) {
memset(vis, false, sizeof(vis));
if(dfs(i)) res++;
}
return res;
} int main() {
#ifndef ONLINE_JUDGE
freopen("Hungary.in","r",stdin);
freopen("Hungary.out","w",stdout);
#endif
int x, y;
read(n), read(m), read(e);//n, m为左右两边点的个数，e为边数
while(e--) {
read(x), read(y);
if(y>m) continue;
jb(x, y);
}
printf("%d\n", Hungary());
return ;
}
2.与网络流有何关系？？？？
将源点和左边的点相连，右边的点与汇点相连，流量设为1；
左右点之间的边流量设为一个大于等于1的整数；
此时求出最大流，即为最大匹配；
感性理解一下：最大匹配是在边集中选出一个子集；一个点与该子集中的边相连，与该点与源点或者汇点所连边的流量流满是等效的；
建边过程：
inline void jb(int u, int v, int w) {
edge[++cnt].to=v;
edge[cnt].next=head[u];
edge[cnt].len=w;
head[u]=cnt;
}
int main() {
int x, y, z;
read(n), read(m), read(s), read(t);
for(int i=;i<=m;i++) {
read(x), read(y), read(z);
jb(x, y, z), jb(y, x, );
}
Dinic::Dinic();
return ;
}