最大流
EdmondsKarp
bfs找路罗丰，途中記錄前驅節(jié)點
讓后從匯點遍歷到起點，找到最小flow
再次遍歷，更新沿途邊
累加答案，繼續(xù)bfs
#define mem(x,y) memset(x,y,sizeof(x))
#define SIZE 1005
const int INF=0x3f3f3f3f;
int G[SIZE][SIZE],pre[SIZE];
bool vst[SIZE];
bool bfs(int s,int t){
queue<int> que;
mem(vst,0);
mem(pre,-1);
pre[s]=s;
vst[s]=true;
que.push(s);
while (!que.empty()) {
int u=que.front();que.pop();
for(int i=s;i<=t;++i){//遍歷所有點
if(G[u][i]&&!vst[i]){
pre[i]=u;
vst[i]=true;
if(i==t)return true;
que.push(i);
}
}
}
return false;
}
int EK(int s,int t){
int ans=0;
while (bfs(s,t)) {
int minflow=INF;
for(int i=t;i!=s;i=pre[i]){
minflow=min(minflow,G[pre[i]][i]);
}
for(int i=t;i!=s;i=pre[i]){
G[pre[i]][i]-=minflow;
G[i][pre[i]]+=minflow;
}
ans+=minflow;
}
return ans;
}
dinic
多路增廣+當前弧優(yōu)化
建圖時候建反向邊（前向星邊id從0開始寇僧，這樣edge[i^1]就是反邊）
首先bfs分層，維護每個點到匯點的距離（每個邊距離都看做1）
然后對分過層的圖dfs沸版，每找到一條通路嘁傀，沿途邊邊權減去流量，反邊加上流量视粮，反復找直到沒有
再次bfs直到沒有
for(int &i=curedge[u];i!=-1;i=edge[i].nxt)
這句當前弧優(yōu)化可能看不懂细办，代碼中有詳細注釋
head[] edge[] 是鏈式前向星
curedge[] 當前弧優(yōu)化使用
#include <queue>
#include <string.h>
#define mem(x,y) memset(x,y,sizeof(x))
#define SIZE 1000
struct node{
int v,nxt,w;//指向那個點 下條邊id 權值
}edge[SIZE*2];
int head[SIZE],curedge[SIZE],dis[SIZE],ecnt,s,t;
inline void init(){
ecnt=0;//從偶數開始都行
mem(head,-1);
}
inline void addedge(int u,int v,int w){
edge[ecnt].v=v;
edge[ecnt].w=w;
edge[ecnt].nxt=head[u];
head[u]=ecnt;
ecnt++;
swap(u,v);//添加反邊
edge[ecnt].v=v;
edge[ecnt].w=0;
edge[ecnt].nxt=head[u];
head[u]=ecnt;
ecnt++;
}
bool bfs(){
mem(dis,-1);//不能少
dis[t]=0;//s是起點，t是終點蕾殴，分層
queue<int> que;
que.push(t);
while(!que.empty()){
int u=que.front();que.pop();
for(int i=head[u];i!=-1;i=edge[i].nxt){
if(dis[edge[i].v]==-1&&edge[i^1].w>0){
dis[edge[i].v]=dis[u]+1;
que.push(edge[i].v);
}
}
}
return dis[s]!=-1;//沒有辦法從s到t返回false
}
int dfs(int u,int v,int flow){
if(u==t)return flow;
int delta=flow;//表示前面輸送過來的流量有多少被擋住了笑撞，初始化為所有
for(int &i=curedge[u];i!=-1;i=edge[i].nxt){
//當前弧優(yōu)化，& 引用是重點
if(dis[u]==dis[edge[i].v]+1&&edge[i].w>0){
int d=dfs(edge[i].v,v,min(delta,edge[i].w));
edge[i].w-=d;edge[i^1].w+=d;
delta-=d;//可以放行d的流量钓觉，被擋住的流量變少了
if(delta==0)break;//這句對當前弧優(yōu)化很重要茴肥，這時進來的流量全都放行了，那么當前這條路可能剛好被填滿议谷，也可能還有寬裕（如果delta炉爆！=0，說明這條路肯定占滿了）
//因為可能有寬裕卧晓，所以這條路以后還要走芬首，這時候break;curedge[u]=i，前面的路因為都滿了逼裆，所以直接舍去郁稍，下次到這個點直接從第i個邊開始，這就是當前弧優(yōu)化胜宇。
}
}
return flow-delta;//送進來的 - 擋住的 = 有效流量
}
int dinic(){
int ans=0;
while (bfs()) {//分層（計算距離）
for(int i=s;i<=t;i++)//每bfs一次耀怜，層次就刷新，所以也要重置當前弧
curedge[i]=head[i];
ans+=dfs(s,t,INF);//從點1到點n最大流桐愉，輸入流量無窮大
}
return ans;
}
費用流
spfa
求最小費用最大流
建邊時候反邊cost是原來的負數
用spfa求出一條s到t的最短路财破，途中
pre[]數組記錄當前點是從哪個邊過來的（放了一個邊id）
然后通過pre[]從t一直遍歷到s，找到途中最小流量Min
再遍歷一次从诲，更新途中邊的容量左痢，更新答案
再次spfa直到沒有通路
#include <queue>
#include <string.h>
#define mem(x,y) memset(x,y,sizeof(x))
#define SIZE 1000
struct node{
int v,nxt,cap,cost;//指向那個點 下條邊id 流通容量 這條路花費(看情況有時候是單價，記得改dfs里面的跟新)
}edge[40010];
int head[SIZE],dis[SIZE],pre[SIZE],ecnt,s,t;
bool vst[SIZE];
inline void init(){
ecnt=0;//從偶數開始都行
mem(head,-1);
}
inline void addedge(int u,int v,int cap,int cost){
edge[ecnt].v=v;
edge[ecnt].cap=cap;
edge[ecnt].cost=cost;
edge[ecnt].nxt=head[u];
head[u]=ecnt;
ecnt++;
swap(u,v);//添加反邊
edge[ecnt].v=v;
edge[ecnt].cap=0;
edge[ecnt].cost=-cost;//注意反邊花費為負
edge[ecnt].nxt=head[u];
head[u]=ecnt;
ecnt++;
}
bool spfa(){
mem(dis,INF);//不能少
mem(vst,0);
mem(pre,-1);
dis[s]=0;//s是起點，t是終點俊性，分層
vst[s]=true;
queue<int> que;
que.push(s);
while(!que.empty()){
int u=que.front();que.pop();
vst[u]=false;
for(int i=head[u];i!=-1;i=edge[i].nxt){
if(dis[u]+edge[i].cost<dis[edge[i].v]&&edge[i].cap>0){
//通過點u更短
dis[edge[i].v]=dis[u]+edge[i].cost;
pre[edge[i].v]=i;
if(!vst[edge[i].v]){
vst[edge[i].v]=true;
que.push(edge[i].v);
}
}
}
}
return pre[t]!=-1;//沒有辦法從s到t返回false
}
int mfmc(int & cost){//cost 按引用更新
int flow=0; cost=0;
while (spfa()) {
int Min=INF;
for(int i=pre[t];i!=-1;i=pre[edge[i^1].v]){//i是邊的id略步，得到另一個頂點edge[i^1].v
if(Min>edge[i].cap){
Min=edge[i].cap;
}
}
for(int i=pre[t];i!=-1;i=pre[edge[i^1].v]){
edge[i].cap-=Min;
edge[i^1].cap+=Min;
}
cost+=dis[t]*Min;
flow+=Min;
}
return flow;
}
