题解 P2488 【[SDOI2011]工作安排】
先吐槽一下时限，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真的好么。。