在vfk的帮助下终于做掉了这题QAQ……vfk建议萌萌哒lzz来放个题解(里面很多是口胡的)

Description

一个二分图，左边$n$个点右边$m$个点。$S$向左边第$i$个点连的边容量为$c_i$，流量为$x$时费用为$a_ix^2+b_ix$。 左边到右边有一些边，容量为无穷大，没有费用。 右边第$j$个点到$T$连的边容量为$d_j$，没有费用。 求最小费用最大流。 $0 \leq a_i,b_i,c_i,d_i \leq 3，a_i+b_i>0，n,m \leq 100$，左边到右边的边数不超过$1000$。

Solution

我们从一个新的角度考虑总费用，假设我们有了一个费用的上界$\lambda$，可以求出费用$\leq \lambda$条件下的最大流，这个函数记为$f(\lambda)$，那么把$f(\lambda)$对$\lambda$积分就能得到答案。

每条边的流量$x_i$都满足$2a_ix_i+b_i \leq \lambda$

将$f(\lambda)$分段积分，分段时保证段内每条边的流量都是关于$\lambda$的一次函数。

那么如何估计段数呢，考虑最小割，一个割的代价是一个关于$\lambda$的一次函数，而且一次函数的斜率取值是$O(n)$的，而最小割是这些割的$\min$相当于半平面交。所以段数是$O(n)$的。

关于有意义的割的数目是$O(n)$的，可以这么考虑，假设缓慢增大某些边的流量，用dinic增广，每个点的level一定是非减的(level=$\infty$表示在T集合)，则割集的变化次数一定不超过$n$。所以至多有$n+1$个有意义的割。

接下来就是把这些断点找出来，可以采用经典的分治办法，先用网络流求出$f(\lambda)$在左右端点的一次函数，然后每次对两条直线求交点，判断交点处的$f(\lambda)$是否符合，不符合说明中间存在其他的半平面，递归左右两边。这样需要$O(n)$次网络流。

最后在整点处需要注意，由于存在$a_i=0$的情况，函数值可能不连续，这时候将跳跃的流量直接乘以费用加入答案里，然后对区间$[i,i+1]$采用分段积分就可以了。

至于实现嘛，有很多要考虑的细节，首先得实现一个分数类。跑网络流时用实数，得到最小割之后用分数计算最小割关于$\lambda$的函数。

分治的时候判断交点$px$是否符合可以看$px+\epsilon$处的函数是否跟右端点函数一样。

其实很(ji)多(hu)关(suo)键(you)姿势都是vfk教我的

//frac是分数类

//带费用限制的网络流(我比较懒每次重新构图)
pair<frac,frac> dinic(DB lambda)//返回函数kx+b的pair(k,b)
{
    tot=1;
    memset(head,0,T+1<<2);
    DB w;
    for(int i=1;i<=n;i++)
    {
        if(A[i]==0)
            addedge(S,i,B[i]>lambda?0:C[i]);
        else
        {
            if(B[i]>lambda)w=0;
            w=(lambda-B[i])/(2.0*A[i]);
            if(w>-feps)
                addedge(S,i,min(w,DB(C[i])));
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(G[i][j])
                addedge(i,n+j,finf);
    for(int i=1;i<=m;i++)
        addedge(n+i,T,D[i]);
    mf=0;
    while(bfs())
        mf+=aug(S,1e10);
    frac k(0),b(0);
    for(int i=1;i<=n;i++)
        if(level[i]==-1)
        {
            if(A[i]==0)
                b+=B[i]>lambda?frac(0):frac(C[i]);
            else
            {
                if(B[i]>lambda)b+=frac(0);
                else if(A[i]*2*C[i]+B[i]>lambda)
                    k+=frac(1,A[i]*2),b-=frac(B[i],A[i]*2);
                else b+=frac(C[i]);
            }
        }
    for(int i=1;i<=m;i++)
        if(level[n+i]!=-1)
            b+=frac(D[i]);
    return make_pair(k,b);
}

//分治求断点

#define fun(_x) MF::dinic(_x)

vector<pair<frac,frac> > bp;//断点

void solve(pair<frac,frac> fl,pair<frac,frac> fr)
{
    if(fl==fr)return;
    frac px=(fr.second-fl.second)/(fl.first-fr.first);
    pair<frac,frac> fml=fun(px.toDB()-eps),fmr=fun(px.toDB()+eps);
    if(fmr==fr)
        bp.push_back(make_pair(px,px*fl.first+fl.second));
    else
    {
        solve(fl,fml);
        solve(fmr,fr);
    }
}