今天接觸了最大流，網上有很多ppt，耐心看下，再敲幾遍代碼大概就能懂意思了
EK 算法
關鍵是要了解要了解反悔的這個意思，因為每次當你選擇了一種方式，但是這種方式不一定是最優的是以我們要再來建立一條反向邊，
來完成反悔的政策
然後就是大概一直找增廣路，改變最大的值，一直到找不到增廣路為止
現在把模闆的代碼附上，并且給予注釋
下面有兩種方式一種是紫書上劉汝佳的代碼，還有種是用鍊式前向星，還有種是dfs的方式，之後會繼續補充
分别給出兩種代碼
struct Edge{
int from,to,cap,flow;
// from:起始邊, to:終點邊 , cap: 容量 , flow: 流量
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}//内建函數
};
struct EdmondsKarp{
int n,m;
vector<Edge> edges;// edges 用來存所有的邊， 正向反向邊都要存
vector<int> G[maxn];//用來記錄第i個點的每條邊的序号
int a[maxn];//用來存增廣路上的可改變的值
int p[maxn];// 用來記錄入-編号
void init(int n){
for(int i=0;i<n;i++)G[i].clear();
edges.clear();
}
void Addedge(int from, int to ,int cap){
// 邊的添加很有技巧
因為可以反悔，是以 我們每次要存入反向邊，反向邊的容量為0
當然有時候，根據題意的不同有時反向邊的容量不為0，那麼就按照題目的給的資料進行存儲
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
m = edges.size();
// 這個也有技巧，其實這個和鍊式前向星很像(兩條變的存儲cnt++，但也是連在一起的，這個也是）
每次将這個點連接配接的邊的序号push進去
G[from].push_back(m-2);
G[to].push_back(m-1);
}
int maxflow(int s,int t){
int flow = 0;
for(;;){
CLR(a);
queue<int> Q;
Q.push(s);
a[s]=inf;
while(!Q.empty()){
int x = Q.front();
Q.pop();
for(int i=0;i<G[x].size();i++){
//通路這個點中的所有邊
Edge& e = edges[G[x][i]];
// e得到這個邊的資訊
if(!a[e.to] && e.cap>e.flow){
//這個部分比較難了解
！a[e.to]最小殘留量為0是才會更新，如果已經不為0說明更新過不再更新
目前的容量必須大于流量
p[e.to]=G[x][i];
// 儲存目前點的标号，用以後面更新
a[e.to]=min(a[x],e.cap-e.flow);
Q.push(e.to);
}
}
if(a[t])break;//如果被更新break
}
if(!a[t])break;
//此時找不到增廣路
for(int u=t;u != s;u = edges[p[u]].from){
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];
}
flow += a[t];
}
return flow;
}
};
下面給出用鍊式前向星代碼
void addedge(int u,int v,int w){//這邊就是一個簡單的鍊式前向星處理
pnt[cnt]=v;
nxt[cnt]=head[u];
cap[cnt]=w;
head[u]=cnt++;
}
void adddouble(int u,int v,int w){//同樣是加邊，兩條
addedge(u,v,w);
addedge(v,u,0);
}
int maxflow(int s,int t){
int flow = 0;
for(;;){
CLR(a);
queue<int> q;
q.push(s);
a[s]=inf;//不要忘記初始化為inf
while(!q.empty()){
int u = q.front();
q.pop();
for(int i=head[u]; ~i; i= nxt[i]){
int v =pnt[i];
if(!a[v] && cap[i] > 0){
a[v]=min(cap[i],a[u]);
pre[v]=i;// 此時的pre也是記錄目前點的标号，記住用鍊式前向星的時候這是i！
q.push(v);
}
}
if(a[t])break;
}
if(!a[t])break;
flow += a[t];
for(int i,u=t;u!=s;u = pnt[i^1]){// 這部分的更新也是。要對鍊式前向星了解才行呢！
i = pre[u];
cap[i] -= a[t];//此時我省略了流量，隻用了流量是以加減就是反着的，了解了解
cap[i^i] += a[t];
}
}
return flow;
}