资料

用最通俗的语言让你学会网络流

1. $ \begin{array}{c}
   \left | f+f' \right | = \left | f \right | +\left | f' \right |
   \end{array}$
   所以，当可行流的残余网络有可行流，原网络的可行流一定不是最大流
2. 对于任何一个可行解，都对应一个可行流 并且 对于任何一个可行流，都对应一个可行解

模板

网络最大流

Dinic算法

#include<bits/stdc++.h>
using namespace std;
const int MX_N=410,MX_M=5100;
struct node{
    int to,next,w;
}edge[MX_M<<1];
int head[MX_N]={0},edge_cnt=0;
inline void Add(int x,int y,int w){
    node &i=edge[edge_cnt];
    i.w=w,i.to=y,i.next=head[x];
    head[x]=edge_cnt++;
}
inline void add(int x,int y,int w){
    Add(x,y,w),Add(y,x,0);
}
int s=0,t=MX_N-1;
int cur[MX_N]={0},dist[MX_N]={0};
bool bfs(){
    for(int i=0;i<MX_N;i++)  cur[i]=head[i],dist[i]=-1;
    queue<int > qu;qu.push(s);dist[s]=0;
    while(!qu.empty()){
        int now=qu.front();qu.pop();
        for(int i=head[now];i!=-1;i=edge[i].next){
            int to=edge[i].to;
            if(dist[to]==-1&&edge[i].w){
                dist[to]=dist[now]+1;
                qu.push(to);
            }
        }
    }
    return dist[t]!=-1;
}
int dfs(int now,int flow){
    if(now==t)  return flow;
    int left=flow;
    for(int &i=cur[now];i!=-1;i=edge[i].next){
        int to=edge[i].to,w=edge[i].w;
        if(dist[to]==dist[now]+1&&w){
            int cur_flow=dfs(to,min(left,w));
            left-=cur_flow;
            edge[i].w-=cur_flow;
            edge[i^1].w+=cur_flow;
            if(left==0)  break;
        }
    }
    if(flow==left)  dist[now]=-1;
    return flow-left;
}
int dinic(){
    int sum=0;
    while(bfs()){
        sum+=dfs(s,0x3f3f3f3f);
    }
    return sum;
}
signed main(){
    memset(head,-1,sizeof(head));
    //=======================================================


    //=======================================================
    return 0;
}

最小费用最大流

EK(Spfa)

#include<bits/stdc++.h>
using namespace std;
const long long MX_N=5010;
const long long MX_M=50100;
struct node{
    long long to,next;
    long long w,cost;
}edge[MX_M<<1];
long long head[MX_N]={0},edge_cnt=0;
inline void add(long long x,long long y,long long w,long long c){
    node& it=edge[edge_cnt];
    it.cost=c;it.next=head[x];it.w=w;it.to=y;
    head[x]=edge_cnt++;
}
long long dis[MX_N]={0};bool flag[MX_N]={0};
long long last_edge[MX_N]={0},last_node[MX_N];
long long n,m,s,t;
bool spfa(){
    for(long long i=1;i<=n;i++)  dis[i]=0x3f3f3f3f,flag[i]=0,last_edge[i]=-1,last_node[i]=0;
    queue<long long > qu;
    qu.push(s);flag[s]=1;dis[s]=0;
    while(!qu.empty()){
        long long now=qu.front();qu.pop();flag[now]=0;
        for(long long i=head[now];i!=-1;i=edge[i].next){
            long long to=edge[i].to,cost=edge[i].cost;
            if(dis[to]>dis[now]+cost&&edge[i].w>0){
                dis[to]=dis[now]+cost;
                last_edge[to]=i;
                last_node[to]=now;
                if(!flag[to]){
                    qu.push(to);flag[to]=1;
                }
            }
        }
    }
    return dis[t]!=0x3f3f3f3f;
}

signed main(){
    memset(head,-1,sizeof(head));
    
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for(long long i=1;i<=m;i++){
        long long u,v,w,c;
        scanf("%lld%lld%lld%lld",&u,&v,&w,&c);
        add(u,v,w,c);
        add(v,u,0,-c);   //反向边负花费
    }
    long long ans_flow=0,ans_cost=0;
    while(spfa()){
        long long cur_flow=0x3f3f3f3f,cur_cost=0;
        for(long long i=t;i!=s;i=last_node[i]){
            cur_flow=min(cur_flow,edge[last_edge[i]].w);
            cur_cost+=edge[last_edge[i]].cost;
        }
        ans_flow+=cur_flow;
        ans_cost+=cur_flow*cur_cost;

        for(long long i=t;i!=s;i=last_node[i]){
            long long now_edge=last_edge[i];
            edge[now_edge].w-=cur_flow;
            edge[now_edge^1].w+=cur_flow;
        }
    }
    printf("%lld %lld",ans_flow,ans_cost);
    return 0;
}

无源汇上下界可行流

#include<bits/stdc++.h>
using namespace std;
const int MX_N=310,MX_M=15010;
struct node{
    int to,next,w;
}edge[MX_M<<1];
int edge_cnt=0,head[MX_N]={0};
inline void Add(int x,int y,int w){
    node &i=edge[edge_cnt];
    i.w=w;i.to=y;i.next=head[x];
    head[x]=edge_cnt++;
}
inline void add(int x,int y,int w){
    Add(x,y,w),Add(y,x,0);
}
int cur[MX_N]={0},dist[MX_N]={0};
int n,s,t;
bool bfs(){
    for(int i=1;i<=n;i++)  dist[i]=-1;
    queue<int > qu;dist[s]=0;qu.push(s);
    while(!qu.empty()){
        int now=qu.front();qu.pop();
        for(int i=head[now];i!=-1;i=edge[i].next){
            int to=edge[i].to;
            if(dist[to]==-1&&edge[i].w){
                dist[to]=dist[now]+1;qu.push(to);
            }
        }
    }
    return dist[t]!=-1;
}
int dfs(int now,int flow){
    if(now==t)  return flow;
    int left=flow;
    for(int &i=cur[now];i!=-1;i=edge[i].next){
        int to=edge[i].to,w=edge[i].w;
        if(dist[to]==dist[now]+1&&w){
            int cur_flow=dfs(to,min(left,w));
            left-=cur_flow;
            edge[i].w-=cur_flow;
            edge[i^1].w+=cur_flow;
            if(left==0)  break;
        }
    }
    if(left==flow)  dist[now]=-1;
    return flow-left;
}
int flw[MX_N]={0};
int lower[MX_M]={0};
signed main(){
    memset(head,-1,sizeof(head));
    int input_n,m;int sum=0;
    scanf("%d%d",&input_n,&m);
    for(int i=1;i<=m;i++){
        int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a+1,b+1,d-c);
        flw[a]-=c;flw[b]+=c;
        lower[i-1]=c;
    }
    /*
      s=1
      t=2+n;
      ni=1+i;
    */
    s=1,t=2+input_n,n=t;
    for(int i=1;i<=input_n;i++){
        if(flw[i]>0){
            add(s,i+1,flw[i]);sum+=flw[i];
        }
        else if(flw[i]<0){   //不能用else
            add(i+1,t,-flw[i]);
        }
    }
    int ans=0;
    while(bfs()){
        for(int i=1;i<=n;i++){
            cur[i]=head[i];
        }
        ans+=dfs(s,0x3f3f3f3f);
    }
    if(ans!=sum){
        printf("NO");return 0;
    }
    printf("YES\n");
    for(int i=0;i<m*2;i+=2){
        printf("%d\n",edge[i^1].w+lower[i/2]);
    }
    return 0;
}