#include <queue>
#include <string.h>
#define mem(x,y) memset(x,y,sizeof(x))
#define SIZE 1000
struct node{
    int v,nxt,w;//指向那個點(diǎn) 下條邊id 權(quán)值
}edge[SIZE*2];
int head[SIZE],curedge[SIZE],dis[SIZE],ecnt,s,t;
inline void init(){
    ecnt=0;//從偶數(shù)開始都行
    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是起點(diǎn)，t是終點(diǎn)，分層
    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){
        //當(dāng)前弧優(yōu)化，& 引用是重點(diǎn)
        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;//這句對當(dāng)前弧優(yōu)化很重要，這時進(jìn)來的流量全都放行了，那么當(dāng)前這條路可能剛好被填滿，也可能還有寬裕（如果delta！=0，說明這條路肯定占滿了）
            //因為可能有寬裕，所以這條路以后還要走，這時候break;curedge[u]=i，前面的路因為都滿了，所以直接舍去，下次到這個點(diǎn)直接從第i個邊開始，這就是當(dāng)前弧優(yōu)化。
        }
    }
    return flow-delta;//送進(jìn)來的 - 擋住的 = 有效流量
}
int dinic(){
    int ans=0;
    while (bfs()) {//分層（計算距離）
        for(int i=s;i<=t;i++)//每bfs一次，層次就刷新，所以也要重置當(dāng)前弧
            curedge[i]=head[i];
        ans+=dfs(s,t,INF);//從點(diǎn)1到點(diǎn)n最大流，輸入流量無窮大
    }
    return ans;
}

費(fèi)用流

spfa

求最小費(fèi)用最大流
建邊時候反邊cost是原來的負(fù)數(shù)
用spfa求出一條s到t的最短路，途中
pre[]數(shù)組記錄當(dāng)前點(diǎn)是從哪個邊過來的（放了一個邊id）
然后通過pre[]從t一直遍歷到s，找到途中最小流量Min
再遍歷一次，更新途中邊的容量，更新答案
再次spfa直到?jīng)]有通路

#include <queue>
#include <string.h>
#define mem(x,y) memset(x,y,sizeof(x))
#define SIZE 1000
struct node{
    int v,nxt,cap,cost;//指向那個點(diǎn) 下條邊id 流通容量 這條路花費(fèi)(看情況有時候是單價，記得改dfs里面的跟新)
}edge[40010];
int head[SIZE],dis[SIZE],pre[SIZE],ecnt,s,t;
bool vst[SIZE];
inline void init(){
    ecnt=0;//從偶數(shù)開始都行
    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;//注意反邊花費(fèi)為負(fù)
    edge[ecnt].nxt=head[u];
    head[u]=ecnt;
    ecnt++;
}
bool spfa(){
    mem(dis,INF);//不能少
    mem(vst,0);
    mem(pre,-1);
    dis[s]=0;//s是起點(diǎn)，t是終點(diǎn)，分層
    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){
                //通過點(diǎn)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，得到另一個頂點(diǎn)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;
}