杭电第二场1005 New Equipments 二次函数离散化+费用流

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6767
题目大意：有n个工人，m个设备。每个工人有3个属性：a[i], b[i], c[i]; 如果第i个人分配第j个设备的代价是 。
输出给i个工人分配设备的最小代价。

思路：典型的费用流，不过m很大，但是根据代价是一个二次函数。我们取对称轴的周围50个点就可以了。然后离散化跑费用流。流量为i时，spfa增广一次就最大流加1.就是给i+1个工人分配设备的最小代价。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL maxn=3000;

struct Mcmf_flow{
    bool vis[maxn];
    LL dis[maxn];
    LL pre[maxn];
    LL last[maxn];
    LL flow[maxn];
    LL zdl, fy;
    LL s1[maxn], sum[maxn], tot=0;
    //dis最小花费;pre每个点的前驱；last每个点的所连的前一条边；flow源点到此处的流量
    struct Edge {
        LL to,next,flow,dis;//flow流量 dis花费
    } e[1000000+10];
    LL head[maxn],cut;
    queue <LL> q;
    int N=0;
    void init(int n){
        N=n;
        memset(s1, 0, sizeof(LL)*(n+60));
        memset(sum, 0, sizeof(LL)*(n+60));
        memset(head,-1,sizeof(LL)*(n+60));
        tot=0;
        cut=-1;//初始化
        zdl=fy=0;
    }

    void add_e(LL from,LL to,LL flow,LL dis) {
        e[++cut].next=head[from];
        e[cut].to=to;
        e[cut].flow=flow;
        e[cut].dis=dis;
        head[from]=cut;
    }

    void add(LL x, LL y, LL z, LL f){
        add_e(x,y,z,f);
        add_e(y,x,0,-f);
    }

    bool spfa(LL s,LL t) {
        memset(dis,0x7f,sizeof(LL)*(N+60));
        memset(flow,0x7f,sizeof(LL)*(N+60));
        memset(vis,0,sizeof(bool)*(N+60));
        q.push(s);
        vis[s]=1; dis[s]=0; pre[t]=-1;
        while (!q.empty()) {
            LL now=q.front();
            q.pop(); vis[now]=0;
            for (LL i=head[now]; i!=-1; i=e[i].next) {
                if (e[i].flow>0 && dis[e[i].to]>dis[now]+e[i].dis) { //正边
                    dis[e[i].to]=dis[now]+e[i].dis;
                    pre[e[i].to]=now;
                    last[e[i].to]=i;
                    flow[e[i].to]=min(flow[now],e[i].flow);//
                    if (!vis[e[i].to]) {
                        vis[e[i].to]=1;
                        q.push(e[i].to);
                    }
                }
            }
        }
        return pre[t]!=-1;
    }

    void MCMF(LL s, LL t) {
        while (spfa(s,t)) {
            LL now=t;
            zdl+=flow[t];
            fy+=flow[t]*dis[t];
            sum[++tot]=fy;//得到sum[]
            s1[tot]=sum[tot]-sum[tot-1];//得到s1[]

            while (now!=s) {
                //从源点一直回溯到汇点
                e[last[now]].flow-=flow[t];//flow和dis容易搞混
                e[last[now]^1].flow+=flow[t];
                now=pre[now];
            }
        }
    }

}min_Flow;

LL a[55], b[55], c[55];
vector<LL> G[55], fy[55];
LL Ls[3000], tot=0;
void getE(int pos, LL m){
    LL x=-b[pos]/(2*a[pos]);
    LL R=max(x, 1LL);
    int sumL=0;
    for(LL i=R; i<=R+25&&i<=m; i++, sumL++){
        G[pos].push_back(i);
        fy[pos].push_back(a[pos]*i*i+b[pos]*i+c[pos]);
        Ls[++tot]=i;
    }
    LL L=min(x-1, m);
    int sumR=50-sumL;
    for(LL i=L; i>=1&&sumR>0; sumR--, i--){
        G[pos].push_back(i);
        fy[pos].push_back(a[pos]*i*i+b[pos]*i+c[pos]);
        Ls[++tot]=i;
    }
    for(LL i=R+sumL; i<=R+sumL+sumR&&i<=m; i++){
        G[pos].push_back(i);
        fy[pos].push_back(a[pos]*i*i+b[pos]*i+c[pos]);
        Ls[++tot]=i;
    }
}

int main() {
    int t, n, m;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        tot=0;
        for(int i=1; i<=n; i++){
            G[i].clear(); fy[i].clear();
        }
        for(int i=1; i<=n; i++){
            scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
            getE(i, m);
        }
        sort(Ls+1, Ls+1+tot);
        int cnt=unique(Ls+1, Ls+1+tot)-Ls-1;
        min_Flow.init(cnt);
        for(int i=1; i<=n; i++){
            for(int k=0; k<G[i].size(); k++){
                int x=lower_bound(Ls+1, Ls+cnt+1, G[i][k])-Ls+50;
                min_Flow.add(i, x, 1, fy[i][k]);
            }
        }
        int S=0, T=cnt+51;
        for(int i=1; i<=n; i++){
            min_Flow.add(S, i, 1, 0);
        }
        for(int i=1; i<=cnt; i++){
            min_Flow.add(i+50, T, 1, 0);
        }
        min_Flow.MCMF(S, T);
        for(int i=1; i<=n; i++){
            printf("%lld%c", min_Flow.sum[i], (i==n)?'\n':' ');
        }
    }
    return 0;
}