[SDOI2011] 工作安排
题目描述
你的公司接到了一批订单。订单要求你的公司提供 \(n\) 类产品，产品被编号为 \(1 \sim n\)，其中第 \(i\) 类产品共需要 \(C_i\) 件。公司共有 \(m\) 名员工，员工被编号为 \(1 \sim m\) 员工能够制造的产品种类有所区别。一件产品必须完整地由一名员工制造，不可以由某名员工制造一部分配件后，再转交给另外一名员工继续进行制造。
我们用一个由 \(0\) 和 \(1\) 组成的 \(m \times n\) 的矩阵 \(A\) 来描述每名员工能够制造哪些产品。矩阵的行和列分别被编号为 \(1 \sim m\) 和 \(1 \sim n\)，\(A_i,j\) 为 \(1\) 表示员工 \(i\) 能够制造产品 \(j\)，为 \(0\) 表示员工 \(i\) 不能制造产品 \(j\)。
如果公司分配了过多工作给一名员工，这名员工会变得不高兴。我们用愤怒值来描述某名员工的心情状态。愤怒值越高，表示这名员工心情越不爽，愤怒值越低，表示这名员工心情越愉快。员工的愤怒值与他被安排制造的产品数量存在某函数关系，鉴于员工们的承受能力不同，不同员工之间的函数关系也是有所区别的。
对于员工 \(i\)，他的愤怒值与产品数量之间的函数是一个 \(S_i+1\) 段的分段函数。当他制造第 \(1 \sim T_{i,1}\) 件产品时，每件产品会使他的愤怒值增加 \(W_{i,1}\)，当他制造第 \(T_{i,1}+1 \sim T_{i,2}\) 件产品时，每件产品会使他的愤怒值增加 \(W_{i,2}\) ……为描述方便，设 \(T_{i,0}=0,T_{i,s_{i+1}}=+\infty\)，那么当他制造第 \(T_{i,j-1}+1 \sim T_{i,j}\) 件产品时，每件产品会使他的愤怒值增加 \(W_{i,j}\)，\(1 \le j \le S_i+1\)。
你的任务是制定出一个产品的分配方案，使得订单条件被满足，并且所有员工的愤怒值之和最小。由于我们并不想使用Special Judge，也为了使选手有更多的时间研究其他两道题目，你只需要输出最小的愤怒值之和就可以了。
输入格式
第一行包含两个正整数 \(m\) 和 \(n\)，分别表示员工数量和产品的种类数；
第二行包含 \(n\) 个正整数，第 \(i\) 个正整数为 \(C_i\)；
以下 \(m\) 行每行 \(n\) 个整数描述矩阵 \(A\)；
下面 \(m\) 个部分，第 \(i\) 部分描述员工 \(i\) 的愤怒值与产品数量的函数关系。每一部分由三行组成：第一行为一个非负整数 \(S_i\)，第二行包含 \(S_i\) 个正整数，其中第 \(j\) 个正整数为 \(T_{i,j}\)，如果 \(S_i=0\) 那么输入将不会留空行（即这一部分只由两行组成）。第三行包含 \(S_i+1\) 个正整数，其中第 \(j\) 个正整数为 \(W_{i,j}\)。
输出格式
仅输出一个整数，表示最小的愤怒值之和。
样例 #1
样例输入 #1
2 3
2 2 2
1 1 0
0 0 1
1
2
1 10
1
2
1 6
样例输出 #1
24
提示
数据范围及约定
- 存在 \(30\%\) 的数据，保证 \(1\le n,m\le 30\)；
- 均匀分布着约 \(30\%\) 的数据，满足 \(S_i = 0\)；
- 均匀分布着约 \(30\%\) 的数据，满足 \(S_i \le 1\)（不包含上述 \(S_i = 0\) 的数据）。
对于全部数据，满足 \(1\le m,n\le 250\)，\(0\le S_i\le 5\)，\(0\le A_{i, j}\le 1\)，\(0< T_{i, j}< T_{i, j + 1}\)，\(0< W_{i,j} < W_{i, j + 1}\)。所有数据均不大于 \(10^5\)。
分析
观察到$W_{i,j} $是递增的，且数据范围较小，所以考虑网络流。
对每个员工每个产品数量区间的花费建一条容量对应区间长度，花费为愤怒值的边，然后跑一遍最小费用最大流即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100,INF=0x7fffffff;
struct edge{int x,y,n,z,sp;}e[N<<1];
struct employer{int s[11],t[11],k;}p[310];
int head[N],cnt=1;
int dep[N],gap[N],nw[N],g[310][310],w[N];
int vis[N],dfn,q[N],pre[N],dis[N];
int n,m,sta,edn,all;
void ad(int x,int y,int z,int sp)
{
e[++cnt].n=head[x];
e[cnt].y=y;
e[cnt].x=x;
e[cnt].z=z;
e[cnt].sp=sp;
head[x]=cnt;
}
void build()
{
int he=1,ta=0;
dep[edn]=1;
q[++ta]=edn;++gap[dep[edn]];
while(he<=ta)
{
int u=q[he++];
for(int i=head[u];i;i=e[i].n)
{
int v=e[i].y;
if(!dep[v] && !e[i].z)
{
dep[v]=dep[u]+1;
q[++ta]=v;++gap[dep[v]];
}
}
}
}
void init()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)scanf("%d",&w[i]);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&g[i][j]);
for(int i=1;i<=n;++i)
{
int pos=0;
scanf("%d",&pos);p[i].k=pos+1;
for(int j=1;j<=pos;++j)
scanf("%d",&p[i].t[j]);
p[i].t[pos+1]=INF;
for(int j=1;j<=pos+1;++j)
scanf("%d",&p[i].s[j]);
}
sta=n+m+1;edn=sta+1;all=edn;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=p[i].k;++j)
{
ad(sta,i,p[i].t[j]-p[i].t[j-1],p[i].s[j]);
ad(i,sta,0,-p[i].s[j]);
}
for(int h=1;h<=m;++h)
{
if(!g[i][h])continue;
ad(i,n+h,INF,0);
ad(n+h,i,0,0);
}
}
for(int i=n+1;i<=n+m;++i)
{
ad(i,edn,w[i-n],0);
ad(edn,i,0,0);
}
}
void ISAP()
{
for(int i=1;i<=all;++i)
dis[i]=INF;
dis[sta]=0;++dfn;
int he=1,ta=0;
q[++ta]=sta;
while(he<=ta)
{
int u=q[he++];
vis[u]=dfn-1;
for(int i=head[u];i;i=e[i].n)
{
int v=e[i].y;
if(e[i].z && dis[v]>dis[u]+e[i].sp)
{
dis[v]=dis[u]+e[i].sp;
pre[v]=i;
if(vis[v]!=dfn){q[++ta]=v;vis[v]=dfn;}
}
}
}
}
long long returnflow()
{
int u=edn,mxflow=INF,spe=0;
while(u!=sta)
{
mxflow=min(e[pre[u]].z,mxflow);
u=e[pre[u]].x;
}
u=edn;
while(u!=sta)
{
e[pre[u]].z-=mxflow;
e[pre[u]^1].z+=mxflow;
spe+=e[pre[u]].sp*mxflow;
u=e[pre[u]].x;
}
return spe;
}
void work()
{
build();
long long mnval=0;
while(1)
{
ISAP();
if(dis[edn]==INF)break;
mnval+=returnflow();
}
cout<<mnval;
}
int main()
{
init();
work();
return 0;
}