BZOJ 2245 [SDOI2011]工作安排

题目大意

给你一堆员工和一堆东西，每个东西一共需要生产Ci个，每个人只能生产指定的东西，每个人生产东西的同时会产生一定的愤怒值，愤怒值是一个分段函数（在不同段里每生产一件产品的愤怒值不一样），求最小的愤怒值总和。

这道题一看到这些对应关系和小得吓人的数据范围一看就是网络流嘛QwQ一看到有两套不同的系统一看就是最小费用最大流嘛QwQ之后这道题就变得很简单了……直接建图跑一发不就好了……

注意这道题为了尽可能压缩时间复杂度必须把有cost的唯一一层放在最接近T的位置上，这样可以节省1倍时间。否则会T.

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=1<<30;
int m,n,c[1000010],intmp,totm,S,T,t[1000010],w[1000010];
int to[1000010],nex[1000010],val[1000010],cost[1000010],head[2000],tot=1;
int dis[2000],from[2000],pre[1000010];
queue<int>q;
bool spfa()
{
    memset(dis,0x3f,sizeof dis);
    memset(from,-1,sizeof from);
    dis[S]=0;
    while(!q.empty()) q.pop();
    q.push(S);
    while(!q.empty())
    {
        int tmp=q.front();
        q.pop();
        //printf("%d\n",tmp);
        for(int i=head[tmp];i;i=nex[i])
            if(val[i]&&dis[to[i]]>dis[tmp]+cost[i])
            {
                dis[to[i]]=dis[tmp]+cost[i];
                from[to[i]]=tmp;
                pre[to[i]]=i;
                q.push(to[i]);
            }
    }
    return ~from[T];
}
long long mincost()
{
    long long ans=0;
    while(spfa())
    {
        int minn=1<<30;
        for(int i=T;i!=S;i=from[i]) minn=min(minn,val[pre[i]]);
        ans+=((long long)minn)*((long long)dis[T]);
        for(int i=T;i!=S;i=from[i]) val[pre[i]]-=minn,val[pre[i]^1]+=minn;
    }
    return ans;
}
void addedge(int tx,int ty,int tz,int tc)
{
    to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz,cost[tot]=tc;
    to[++tot]=tx,nex[tot]=head[ty],head[ty]=tot,val[tot]=0,cost[tot]=-tc;
}
int main()
{
    scanf("%d%d",&m,&n);
    totm=m<<1;
    S=0,T=totm+n+1;
    for(int i=1;i<=n;++i) scanf("%d",c+i);
    for(int i=1;i<=m;++i)
        for(int j=1;j<=n;++j)
        {
            scanf("%d",&intmp);
            if(intmp==1) addedge(m+j,i,INF,0);
        }
    for(int i=1;i<=m;++i)
    {
        scanf("%d",&intmp);
        for(int j=1;j<=intmp;++j) scanf("%d",t+j);
        for(int j=1;j<=intmp+1;++j) scanf("%d",w+j);
        for(int j=1;j<=intmp;++j) addedge(i,T,t[j]-t[j-1],w[j]);
        addedge(i,T,INF,w[intmp+1]);
    }
    for(int i=1;i<=n;++i) addedge(S,m+i,c[i],0);
    printf("%lld\n",mincost());
}