网络流（最大流入门）

网络流之最大流算法入门

网络流算法基于增广路算法：

我们可知由​​

​源点S--->汇点T​

​​有多条路径，增广路算法便是找每一条​

​S--->T​

​​的路，进行操作，对网络流进行更新，当所有路找完后，得到最大流。

最大流之bfs()进行分层：

利用​​

​bfs()对S--->T​

​​的每一个节点进行分层，可以提高算法的效率

代码：

#include<bits/stdc++.h>
using namespace std;
//对网络流进行分层
#define maxn 1005
vector<int>vec[maxn];//vector建图
int dist[maxn];//分层数组
int n,m;//n个点,m条边
void bfs(int s,int t)//源点到汇点
{
    queue<int>q;
    q.push(s);//将源点压入
    dist[s]=1;//节点s代表第一层
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=0; i<vec[x].size(); i++)
        {
            int v=vec[x][i];
            if(dist[v]==-1)
            {
                q.push(v);
                dist[v]=dist[x]+1;

            }
        }
    }

}
int main()
{
    memset(dist,-1,sizeof(dist));
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        vec[u].push_back(v);
    }
    bfs(1,n);
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",dist[i]);
    }

}      

如上图，入度为0的是源点，出度为0的是汇点输入数据后得到的：

化为表格：

dist[ ]	每个节点代表的层次
dis[1]	1
dist[2]	2
dist[3]	3
dist[4]	2
dist[5]	3
dist[6]

#include<bits/stdc++.h>
 
using namespace std;
 
const int MAXN=2010;
const int MAXM=1200010;
const int INF=0x3f3f3f3f;
 
struct Edge{
    int to,next,cap,flow;
}edge[MAXM];
int tol,head[MAXN];
 
void init()
{
    tol=2;
    memset(head,-1,sizeof(head));
}
 
void addedge(int u,int v,int w,int rw=0)
{
    edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=0;
    edge[tol].next=head[u];head[u]=tol++;
    edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=0;
    edge[tol].next=head[v];head[v]=tol++;
}
 
int Q[MAXN];
int dep[MAXN],cur[MAXN],sta[MAXN];
 
bool bfs(int s,int t,int n)
{
    int front=0,tail=0;
    memset(dep,-1,sizeof(dep[0])*(n+1));
    dep[s]=0;
    Q[tail++]=s;
    while(front<tail){
        int u=Q[front++];
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;
            if(edge[i].cap>edge[i].flow&&dep[v]==-1){
                dep[v]=dep[u]+1;
                if(v==t){
                    return true;
                }
                Q[tail++]=v;
            }
        }
    }
    return false;
}
 
int dinic(int s,int t,int n)
{
    int maxflow=0;
    while(bfs(s,t,n)){
        for(int i=0;i<n;i++){
            cur[i]=head[i];
        }
        int u=s,tail=0;
        while(cur[s]!=-1){
            if(u==t){
                int tp=INF;
                for(int i=tail-1;i>=0;i--){
                    tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
                }
                maxflow+=tp;
                for(int i=tail-1;i>=0;i--){
                    edge[sta[i]].flow+=tp;
                    edge[sta[i]^1].flow-=tp;
                    if(edge[sta[i]].cap-edge[sta[i]].flow==0){
                        tail=i;
                    }
                }
                u=edge[sta[tail]^1].to;
            }else if(cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to]){
                sta[tail++]=cur[u];
                u=edge[cur[u]].to;
            }else{
                while(u!=s&&cur[u]==-1){
                    u=edge[sta[--tail]^1].to;
                }
                cur[u]=edge[cur[u]].next;
            }
        }
    }
    return maxflow;
}
 
int main()
{
    int n,m,s,t;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    int u,v,w;
    init();
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
    }
    printf("%d\n",dinic(s,t,n));
    return 0;
}