传送门
Description
申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。经过估算,这个项目需要N 天才能完成,其中第i 天至少需要Ai 个人。 布布通过了解得知,一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天,招募费用是每人Ci 元。新官上任三把火,为了出色地完成自己的工作,布布希望用尽量少的费用招募足够的志愿者,但这并不是他的特长!于是布布找到了你,希望你帮他设计一种最优的招募方案。
Solution
最小费用最大流
把每一个点都看成是一条边,边的流量上限是(inf-w[i]),费用是(0),然后每个覆盖都是(L-1)向(R)连一条流量(inf),费用是(C[k])的边,最有一个点向(T)连流量(inf)的边,这样,我们就控制了最大流一定(inf),而每个点就至少有(w[i])个流量是从有费用的边上走啦。
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
#define inf 0x3f3f3f3f
#define ME 25005
#define MN 5005
int n,m,S,T,maxflow;
ll mincost;
struct edge{int to,w,c,nex;}e[ME];int hr[MN],cnt=1;
inline void ins(int f,int t,int w,int c)
{
e[++cnt]=(edge){t,w,c,hr[f]};hr[f]=cnt;
e[++cnt]=(edge){f,0,-c,hr[t]};hr[t]=cnt;
}
int d[MN],q[ME],l,r;
bool inq[MN],vis[MN];
bool spfa()
{
memset(d,0x3f,sizeof d);
q[l=r=MN]=T;d[T]=0;inq[T]=1;
while(l<=r)
{
int u=q[l++];inq[u]=0;
for(int i=hr[u];i;i=e[i].nex)
if(e[i^1].w&&d[e[i].to]>d[u]-e[i].c)
{
d[e[i].to]=d[u]-e[i].c;
if(!inq[e[i].to])
d[e[i].to]<d[q[l]]?q[--l]=e[i].to:q[++r]=e[i].to,inq[e[i].to]=1;
}
}
return d[S]!=inf;
}
int flow(int x,int f)
{
vis[x]=1;
if(x==T) return f;
int used=0,w;
for(int i=hr[x];i;i=e[i].nex)
if(!vis[e[i].to]&&d[x]-e[i].c==d[e[i].to]&&e[i].w)
{
w=flow(e[i].to,min(f-used,e[i].w));
used+=w;mincost+=1ll*w*e[i].c;
e[i].w-=w,e[i^1].w+=w;
if(f==used) return f;
}
return used;
}
inline void solve()
{
while(spfa())
{
do{
memset(vis,0,sizeof vis);
maxflow+=flow(S,inf);
}while(vis[T]);
}
}
int main()
{
int i,u,v;
n=read(),m=read();
S=0,T=n+1;
for(i=1;i<=n;++i) ins(i-1,i,inf-read(),0);
ins(n,n+1,inf,0);
for(i=1;i<=m;++i) u=read(),v=read(),ins(u-1,v,inf,read());
solve();
printf("%lld
",mincost);
return 0;
}
Blog来自PaperCloud,未经允许,请勿转载,TKS!