杭电第二场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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:31
以前小时候我最痛恨出轨、偷情的人,无论男女,为什么会出轨?现在我成了自己最讨厌的人,没想到分享的东西在牛客会被这么多人看,大家的评价都很中肯,我也认同,想过一一回复,但我还是收声了,我想我应该说说这件事,这件事一直压在我心里,是个很大的心结,上面说了人为什么出轨,我大概能明白了。我们大一下半年开始恋爱,开始恋爱,我给出了我铭记3年的承诺,我对她好一辈子,我永远不会背叛,我责任心太重,我觉得跟了我,我就要照顾她一辈子,我们在一起3年我都没有碰过她,她说往东我就往东,她说什么我做什么,她要我干什么,我就干什么!在学校很美好,中途也出过一些小插曲,比如男闺蜜、男闺蜜2号等等等。但我都强迫她改掉了,我...
牛客刘北:两个缺爱的人是没有办法好好在一起的,但世界上哪有什么是非对错?你后悔你们在一起了,但是刚刚在一起的美好也是真的呀,因为其他人的出现,你开始想要了最开始的自己,你的确对不起自己,21岁的你望高物远,你完全可以不谈恋爱,去过你想要的生活,你向往自由,在一起之后,你要想的不是一个人,而是两个人,你不是变心了,就像你说的,你受够了,你不想包容了,冷静几天是你最优的选择,爱人先爱己。
社会教会你的第一课
点赞 评论 收藏
分享
一表renzha:手写数字识别就是一个作业而已
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务