前言

Ouuan Orz

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

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

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

当然，这时(Ouuan)说的。

算法讲解

要求

(st)无入边，(ed)无出边。
可以有负环。

无源汇最小费用流

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

没有(st)和(ed)，同时最小化(sumlimits_{(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^2log{U}))，(U)是边中的最大流量。

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

#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++)
	{
//		if(a[i].d>0)sum+=a[i].d;
		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
",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)吧，学这个算法就图一乐。

参考资料

洛谷的讨论

弱多项式复杂度算法非常非常好的常考资料，真的非常非常好

坑

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

代码也要补点注释。