「题解」「NOI2008」志愿者招募 employee

一道奇特的 费用流 问题。

题目链接:Luogu P3980/BZOJ 1061/NOI2008 D1T3。

题目

题目描述

申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。经过估算,这个项目需要 $n$ 天才能完成,其中第 $i$ 天至少需要 $a_i$ 个人。布布通过了解得知,一共有 $m$ 类志愿者可以招募。其中第 $i$ 类可以从第 $s_i$ 天工作到第 $t_i$ 天,招募费用是每人 $c_i$ 元。新官上任三把火,为了出色地完成自己的工作,布布希望用尽量少的费用招募足够的志愿者,但这并不是他的特长!于是布布找到了你,希望你帮他设计一种最优的招募方案。

数据范围

变量数据范围
$n$$[1,10^3]$
$m$$[1,10^4]$

时空限制

题目时间限制空间限制
Luogu P3980$2\text{s}$$125\text{MiB}$
BZOJ 1061$20\text{s}$$162\text{MiB}$
NOI2008 D1T3$2\text{s}$$125\text{MiB}$

题解

思路

这道题的思路比较新奇(我太菜了),有人说跟思路来源和线性规划有关。

建图:

  • $s=0,t=n+1$,连边 $(s,1,\texttt{INF},0),(n,t,\texttt{INF},0)$。
  • $\forall i\in [1,n]$,有一条边 $(i,i+1,\texttt{INF}-a_i,0)$。
  • 对于每对 $s_i,t_i,c_i$,有一条边 $(s_i,t_i+1,\texttt{INF},c_i)$。

然后跑一边费用流即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=1000+5;
const int MAXM=10000+5;

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int n,m;
int cnt=1,head[MAXN],to[(MAXN+MAXM)<<1],w[(MAXN+MAXM)<<1],p[(MAXN+MAXM)<<1],Next[(MAXN+MAXM)<<1];

inline void Add_Edge(reg int u,reg int v,reg int len,reg int val){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    p[cnt]=val;
    head[u]=cnt;
    return;
}

inline void Add_Tube(reg int u,reg int v,reg int len,reg int val){
    Add_Edge(u,v,len,val);
    Add_Edge(v,u,0,-val);
    return;
}

inline void Read(void){
    n=read(),m=read();
    for(reg int i=1;i<=n;++i){
        static int x;
        x=read();
        Add_Tube(i,i+1,INF-x,0);
    }
    for(reg int i=1;i<=m;++i){
        static int s,t,c;
        s=read(),t=read(),c=read();
        Add_Tube(s,t+1,INF,c);
    }
    return;
}

bool inque[MAXN];
int dis[MAXN];
queue<int> Q;

inline bool SPFA(int s,reg int t){
    memset(inque,false,sizeof(inque));
    memset(dis,0X3F,sizeof(dis));
    while(!Q.empty())Q.pop();
    inque[s]=true,dis[s]=0,Q.push(s);
    while(!Q.empty()){
        reg int ID=Q.front();
        Q.pop();
        inque[ID]=false;
        for(reg int i=head[ID];i;i=Next[i])
            if(dis[to[i]]>dis[ID]+p[i]&&w[i]>0){
                dis[to[i]]=dis[ID]+p[i];
                if(!inque[to[i]]){
                    inque[to[i]]=true;
                    Q.push(to[i]);
                }
            }
    }
    return dis[t]!=INF;
}

bool vis[MAXN];
int cur[MAXN];
int MinCost;

inline int DFS(reg int ID,reg int t,reg int lim){
    if(ID==t){
        MinCost+=lim*dis[t];
        return lim;
    }
    vis[ID]=true;
    reg int flow=0;
    for(reg int &i=cur[ID];i;i=Next[i])
        if(dis[to[i]]==dis[ID]+p[i]&&w[i]>0&&!vis[to[i]]){
            reg int f=DFS(to[i],t,min(lim-flow,w[i]));
            if(f){
                flow+=f;
                w[i]-=f;
                w[i^1]+=f;
                if(flow==lim)
                    break;
            }
        }
    vis[ID]=false;
    return flow;
}

inline int Dinic(reg int s,reg int t){
    reg int res=0;
    while(SPFA(s,t)){
        memcpy(cur,head,sizeof(head));
        res+=DFS(s,t,INF);
    }
    return res;
}

inline void Work(void){
    reg int s=0,t=n+1;
    Add_Tube(s,1,INF,0);
    Dinic(s,t);
    printf("%d\n",MinCost);
    return;
}