前言

Ouuan Orz

当然，先说一下弱多项式是啥？

OI 界中叫做 Dinic 和 EK 的那两个最大流算法，把其中的 BFS 改成求最短路，复杂度都是与值域多项式相关的，即复杂度是伪多项式的。

多项式复杂度有弱多项式和强多项式两种，弱多项式就是关于输入长度（ $n$、 $m$ 之类的，以及 $log 值域$ ）为多项式复杂度，强多项式就是在加减乘除为 $O(1)$ 时复杂度关于数据规模为多项式（就是说跟值域完全无关，只和 $n, m$ 之类的相关，复杂度关于 $n, m$ 之类的为多项式）。

当然，这时 Ouuan 说的。

算法讲解

要求

  1. $st$ 无入边，$ed$ 无出边。
  2. 可以有负环。

无源汇最小费用流

对于有源汇最小费用最大流的定义我们改一下：

没有 $st$ 和 $ed$，同时最小化 $\sum\limits_{(i,j)∈E} cost(i,j)*f(i,j)$ 。

当然，这个时候你可能会好奇这个我们讲的有源汇最小费用最大流有个 $der$ 的关系？

那如果我们从 $ed$ 向 $st$ 连接一条无限小的边，使得流量越多越好，然后后面减掉就行了。

做法

首先，这个流是最小费用当且仅当图中不存在负环，证明和上篇重制版最小费用最大流博客雷同，不予以赘述。

首先明白一个定理：如果把每条边容量乘 $2$，则对应流量乘 $2$，最小费用乘 $2$，因为乘 $2$ 一定不存在负环。

那么接下来就非常简单了，把边权拆成二进制，维护残余网络 $G$ ，一开始 $G$ 中的容量和流量都为 $0$，然后二进制从高到低扫描，每一位把所有边的容量和流量乘 $2$，但是需要注意，有些边这一位二进制可能为 $1$，因此这条边会加入到残余网络中，这就非常的蛋疼了，好的方法是这条边是 $(x,y)$，在加入前从 $y$ 跑一遍最短路，如果 $d[x]+cost(x,y)<0$ ，那么就不加入，并且把 $y$ 到 $x$ 的最短路的流量全部减一，当然，如果这条边原本就存在，则直接流量 $+1$ 即可。

至于为什么直接跑最短路即可，因为我们维护的残余网络中一定没有负环啊。

时间复杂度： $O(nm^2\log{U})$ ，$U$ 是边中的最大流量。

例题：https://uoj.ac/problem/487

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<cstdio>
#include<cstring>
#define N 5100
#define M 110000
using namespace std;
typedef long long LL;
template<class T>
inline T mymin(T x,T y){return x<y?x:y;}
template<class T>
inline T mymax(T x,T y){return x>y?x:y;}
int n,m;
struct node
{
    int x,y,next;
    LL c/*表示它们现在现有的流量*/,d;
}a[M];int len=1,last[N];
LL cap[N];//表示它们原本的流量 
inline void ins_node(int x,int y,LL c,LL d){len++;a[len].x=x;a[len].y=y;a[len].d=d;cap[len]=c;a[len].next=last[x];last[x]=len;}
inline void ins(int x,int y,LL c,LL d){ins_node(x,y,c,d);ins_node(y,x,0,-d);}
//SPFA
LL d[N];
int list[N],head,tail,pre[N];
bool v[N],vv[N];
void spfa(int st,int ed)
{
    list[head=1]=st;tail=2;
    memset(d,20,sizeof(d));d[st]=0;
    memset(pre,0,sizeof(pre));
    memset(v,0,sizeof(v));v[st]=1;
    while(head!=tail)
    {
        int x=list[head++];if(head==n+1)head=1;
        v[x]=0;
        for(int k=last[x];k;k=a[k].next)
        {
            int y=a[k].y;
            if(a[k].c>0 && d[y]>d[x]+a[k].d)
            {
                d[y]=d[x]+a[k].d;
                pre[y]=k;
                if(!v[y])
                {
                    v[y]=1;
                    list[tail++]=y;
                    if(tail==n+1)tail=1;
                }
            }
        }
    }
}
LL cost=0,ans=0,ffuck=0;
void trash(int st,int ed)
{
    LL mmax=0/*,sum=0用来记录st-ed添加的那一条边应该是多少*/,summ=0;
    for(int i=2;i<=len;i++)
    {
        summ+=cap[i];
        mmax=mymax(mmax,cap[i]);
    }
    ins(ed,st,summ,-(LL)999999999);
    mmax=mymax(mmax,cap[len-1]);
    int l=1;
    while(((LL)1<<l)-1<mmax)l++;
    
    for(int ll=l;ll>=1;ll--)//从高位到低位开始扫描二进制 
    {
        cost<<=1;
        LL shit=((LL)1<<(ll-1));
        memset(vv,0,sizeof(vv));
        for(int i=2;i<=len;i++)
        {
            a[i].c<<=1;
            if(a[i].c)a[i].c+=(cap[i]&shit)>0,vv[i]=1;
        }
        //对于所有已经存在的边不用扫描 
        for(int i=2;i<=len;i++)
        {
            if(vv[i])continue;
            if(cap[i]&shit)//反向边绝对不会进来 
            {
                int x=a[i].x,y=a[i].y;
                spfa(y,x);
                if(d[x]+a[i].d<0/*负环!!!!*/)
                {
                    cost+=a[i].d;
                    x=pre[x];
                    while(x)
                    {
                        cost+=a[x].d;
                        a[x].c--;a[x^1].c++;
                        x=pre[a[x].x];
                    }
                    a[i^1].c++;
                }
                else a[i].c++;
            }
        }
    }
    for(int k=last[st];k;k=a[k].next)
    {
        if(!(k&1))ans+=cap[k]-a[k].c;
    }
    printf("%lld %lld\n",ans,cost-(cap[len-1]-a[len-1].c)*a[len-1].d+ffuck);
}
int main()
{
    int st,ed;
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    for(int i=1;i<=m;i++)
    {
        int x,y;LL c,d;scanf("%d%d%lld%lld",&x,&y,&c,&d);
        if(x==y)
        {
            if(d<0)ffuck+=c*d;//自环 
        }
        else ins(x,y,c,d);
    }
    trash(st,ed);
    return 0;
}

细节

无限小？

坑

边权？

坑

总结

放心，因为比赛一般都是构图题，难以卡掉 $ZKW$ 和 $EK$，所以，大胆的，放心的用 $ZKW$ 吧，学这个算法就图一乐。

参考资料

洛谷的讨论：https://www.luogu.com.cn/discuss/show/161006

弱多项式复杂度算法非常非常好的常考资料，真的非常非常好：https://ouuan.github.io/post/%E5%9F%BA%E4%BA%8E-capacity-scaling-%E7%9A%84%E5%BC%B1%E5%A4%9A%E9%A1%B9%E5%BC%8F%E5%A4%8D%E6%9D%82%E5%BA%A6%E6%9C%80%E5%B0%8F%E8%B4%B9%E7%94%A8%E6%B5%81%E7%AE%97%E6%B3%95/

坑

要准备 NOIP 啦，赛后补充 Dij 的做法，还有亿点细节补充。

代码也要补点注释。

赛前还是直接打个简单思路就去准备比赛了。