自动搬运

查看原文

来自洛谷，原作者为

	revenger **

搬运于2025-08-24 21:38:16，当前版本为作者最后更新于2017-04-25 14:37:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先吐槽一下时限，0.5s什么鬼，不应该是1s么。。

好吧回到正题，先观察数据范围，n,m<=250，这是明显的网络流的数据范围。

所以我们就来建一下图。

如果抛开分段函数，这道题的建图思路应该非常清晰，S往人连费用为愤怒值的边，人往能加工的产品连流量inf，费用为0的边，产品往T连流量为ci，费用为0的边，跑一遍费用流即可。

但是怎么处理分段函数呢。看一下分段函数的段非常少，那我们可以拆边。把S往人连的费用为愤怒值的边按照分段函数进行拆分，拆解成si+1条边，前si条边的流量就等于ti-t(i-1)，费用就等于这一段的愤怒值wi，第si+1条边的流量为inf，费用为w(i+1)。这样子拆完边后，跑一遍费用流就可以了。

顺便分享一下之前的思路：把人拆点，每个人拆成si+1个点，往每个点连拆出来的边，这样子会导致边数暴增。但是在BZOJ上依旧能过，洛谷上会被卡掉。所以最后我发现我怎么这么蠢呢，直接拆边不就好了么。。。

附跑的比大陆记者还慢的代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int head[1010],nxt[500010],point[500010],remain[500010],sum;
long long w[500010];
int lastedge[1010],exist[1010];
long long dis[1010];
int wi[1010],si[255][255];
int ti[10],ci[10];
int n,m,x;
const int inf=1e9+7;
const long long longinf=(1ll<<50);
queue<int>q;
#define min(a,b) (a<b?a:b)
void read(int &ans,char ch=getchar())
{
    ans=0;
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';ans=ans*10+ch-48,ch=getchar());
} 
void add(int x,int y,int flow,int cost)
{
    ++sum;nxt[sum]=head[x];head[x]=sum;point[sum]=y;remain[sum]=flow;w[sum]=cost;
    ++sum;nxt[sum]=head[y];head[y]=sum;point[sum]=x;remain[sum]=0;w[sum]=-cost;
}
int addflow(int s,int t)
{
    int now=t,f=inf;
    while(now!=s)
    {
        f=min(f,remain[lastedge[now]]);
        now=point[lastedge[now]^1];
    }
    now=t;
    while(now!=s)
    {
        remain[lastedge[now]]-=f;
        remain[lastedge[now]^1]+=f;
        now=point[lastedge[now]^1];
    }
    return f;
}
bool spfa(int s,int t,int &maxflow,long long &mincost)
{
    memset(dis,127,sizeof(dis));
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int now=q.front();q.pop();
        exist[now]=0;
        for(int tmp=head[now];tmp!=-1;tmp=nxt[tmp])
        {
            int u=point[tmp];
            long long v=w[tmp];
            if(dis[u]>dis[now]+v&&remain[tmp])
            {
                dis[u]=dis[now]+v;
                lastedge[u]=tmp;
                if(!exist[u])
                q.push(u),exist[u]=1;
            }
        } 
    }
    if(dis[t]>longinf) return false;
    int flow=addflow(s,t);
    maxflow+=flow;
    mincost+=flow*dis[t];
    return true;
} 
void mfmc(int s,int t,int &maxflow,long long &mincost)
{
    mincost=maxflow=0;
    while(spfa(s,t,maxflow,mincost));
}
int main()
{
    sum=-1;
    memset(nxt,-1,sizeof(nxt));
    memset(head,-1,sizeof(head));
    read(n),read(m);
    for(int i=1;i<=m;i++)
    {
        read(x);
        add(i+n,m+n+1,x,0);
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    read(si[i][j]);
    for(int i=1;i<=n;i++)
    {
        read(x);
        for(int j=1;j<=x;j++)
        read(ti[j]);
        for(int j=1;j<=x+1;j++)
        read(ci[j]);
        for(int j=1;j<=x;j++)
        add(0,i,ti[j]-ti[j-1],ci[j]);
        add(0,i,inf,ci[x+1]);
        for(int j=1;j<=m;j++)
        if(si[i][j])
        add(i,j+n,inf,0);
    }
    int mflow;
    long long mcost;
    mfmc(0,m+n+1,mflow,mcost);
    printf("%lld",mcost);
} 
最后，再吐槽一遍时限，不放1s真的好么。。