跳转至

网络流

最大流

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
namespace MaxFlow
{
    struct edge{int nex,to,flow;}e[MAX<<1];
    int head[MAX],cnt=1;
    inline void add(int x,int y,int z) {e[++cnt].nex=head[x],head[x]=cnt,e[cnt].to=y,e[cnt].flow=z;}
    inline void Add(int x,int y,int z) {add(x,y,z),add(y,x,0);}

    int N,s,t;
    int maxflow,d[MAX],pre[MAX];
    queue<int> q;
    inline bool Layer()
    {
        fill(d+1,d+N+1,0);
        while(!q.empty()) q.pop();
        d[s]=1,pre[s]=head[s],q.emplace(s);
        while(!q.empty())
        {
            int now=q.front(); q.pop();
            for(int i=head[now];i;i=e[i].nex)
            {
                int to=e[i].to,flow=e[i].flow;
                if(!d[to]&&flow)
                {
                    d[to]=d[now]+1,pre[to]=head[to],q.emplace(to);
                    if(to==t) return 1;
                }
            }
        }
        return 0;
    }
    int Dinic(int now,int flow)
    {
        if(now==t) return flow;
        int rest=flow;
        for(int i=pre[now];i;i=e[i].nex)
        {
            pre[now]=i; int to=e[i].to;
            if(d[to]==d[now]+1&&e[i].flow)
            {
                int k=Dinic(to,min(e[i].flow,rest));
                if(!k) d[to]=0;
                e[i].flow-=k,e[i^1].flow+=k,rest-=k;
                if(!rest) break;
            }
        }
        return flow-rest;
    }
    inline void Work() {while(Layer()) maxflow+=Dinic(s,INF);}
}

费用流

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
namespace MaxFlowMinCost
{
    struct edge{int nex,to,flow,val;}e[MAX<<1];
    int head[MAX],cnt=1;
    inline void add(int x,int y,int flow,int val) {e[++cnt].nex=head[x],head[x]=cnt,e[cnt].to=y,e[cnt].flow=flow,e[cnt].val=val;}
    inline void Add(int x,int y,int flow,int val) {add(x,y,flow,val),add(y,x,0,-val);}

    int N,s,t;
    int maxflow,mincost;
    int dis[MAX],vis[MAX],incf[MAX],pre[MAX];
    queue<int> q;
    inline bool SPFA()
    {
        fill(vis+1,vis+N+1,0),fill(dis+1,dis+N+1,INF);
        vis[s]=1,dis[s]=0,incf[s]=INF,q.emplace(s);
        while(!q.empty())
        {
            int now=q.front(); q.pop();
            vis[now]=0;
            for(int i=head[now];i;i=e[i].nex)
            {
                int to=e[i].to,flow=e[i].flow,val=e[i].val;
                if(!flow) continue;
                if(dis[to]>dis[now]+val)
                {
                    dis[to]=dis[now]+val,incf[to]=min(incf[now],flow),pre[to]=i;
                    if(!vis[to]) vis[to]=1,q.emplace(to);
                }
            }
        }
        return dis[t]!=INF;
    }
    inline void Augment()
    {
        int now=t; maxflow+=incf[t],mincost+=incf[t]*dis[t];
        while(now!=s) {int i=pre[now]; e[i].flow-=incf[t],e[i^1].flow+=incf[t],now=e[i^1].to;}
    }
    inline void Work() {while(SPFA()) Augment();}
}

有源汇上下界网络流

连边时需要记录 in 和 out 数组。Work(typ) 来调用不同功能，\(0\) 为可行流，\(1\) 为最大流，\(2\) 为最小流。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
namespace FeasibleFlow
{
    struct edge{int nex,to,flow;}e[MAX<<1];
    int head[MAX],down[MAX<<1],cnt=1;
    inline void add(int x,int y,int z) {e[++cnt].nex=head[x],head[x]=cnt,e[cnt].to=y,e[cnt].flow=z;}
    inline void Add(int x,int y,int l,int r) {add(x,y,r-l),down[cnt]=l,add(y,x,0);}

    int N,s,t,S,T,tot,flag;
    int maxflow,realflow,d[MAX],pre[MAX];
    int in[MAX],out[MAX];
    queue<int> q;
    inline bool Layer()
    {
        fill(d+1,d+N+1,0);
        while(!q.empty()) q.pop();
        d[S]=1,pre[S]=head[S],q.emplace(S);
        while(!q.empty())
        {
            int now=q.front(); q.pop();
            for(int i=head[now];i;i=e[i].nex)
            {
                int to=e[i].to,flow=e[i].flow;
                if(!d[to]&&flow)
                {
                    d[to]=d[now]+1,pre[to]=head[to],q.emplace(to);
                    if(to==T) return 1;
                }
            }
        }
        return 0;
    }
    int Dinic(int now,int flow)
    {
        if(now==T) return flow;
        int rest=flow;
        for(int i=pre[now];i;i=e[i].nex)
        {
            pre[now]=i; int to=e[i].to;
            if(d[to]==d[now]+1&&e[i].flow)
            {
                int k=Dinic(to,min(e[i].flow,rest));
                if(!k) d[to]=0;
                e[i].flow-=k,e[i^1].flow+=k,rest-=k;
                if(!rest) break;
            }
        }
        return flow-rest;
    }
    inline void Work(int typ)
    {
        S=N+1,T=N+2,N+=2,flag=1;
        for(int i=1;i<=n;++i) if(in[i]>out[i]) Add(S,i,0,in[i]-out[i]),tot+=in[i]-out[i]; else if(in[i]<out[i]) Add(i,T,0,out[i]-in[i]);
        Add(t,s,0,INF);
        while(Layer()) maxflow+=Dinic(S,INF);
        if(tot!=maxflow) flag=0;
        if(!flag||!typ) return;
        realflow=e[cnt].flow,e[cnt].flow=e[cnt-1].flow=0;
        if(typ==1) {S=s,T=t; while(Layer()) realflow+=Dinic(S,INF);}
        if(typ==2) {S=t,T=s; while(Layer()) realflow-=Dinic(S,INF);}
    }
}