bzoj1061 志愿者招募 [最小费用最大流]

in 题目 with 0 comment

Description

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


Input

  第一行包含两个整数N, M,表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负整数,表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci,含义如上文所述。为了方便起见,我们可以认为每类志愿者的数量都是无限多的。


Output

仅包含一个整数,表示你所设计的最优方案的总费用。


Sample Input

3 3
2 3 4
1 2 2
2 3 5
3 3 2


Sample Output

14


HINT

$ 1 \le N \le 1000,1 \le M \le 10000,$ 题目中其他所涉及的数据均不超过$2^{31}-1$。


Solution

费用流A的第一题QAQ,神建图,具体看byvoid大佬的讲解吧
https://www.byvoid.com/zhs/blog/noi-2008-employee


Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define maxn 1010
#define maxe 52100
#define INF 0x3f3f3f3f
//#define DEBUG
using namespace std;
int n,m,S,T,cnt;
int demond[maxn];
int head[maxn],dis[maxn],prev[maxn],path[maxn];

struct edge
{
    int next,to,cap,val;
}e[maxe];

inline int read()
{
    char ch;
    int read=0,sign=1;
    do
        ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-');
    if(ch=='-') sign=-1,ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        read=read*10+ch-'0';
        ch=getchar();
    }
    return sign*read;
}

inline void ins(int u,int t,int v,int c)
{
    cnt++;
    e[cnt].to=t;
    e[cnt].val=v;
    e[cnt].cap=c;
    e[cnt].next=head[u];
    head[u]=cnt;
}

inline void insert(int u,int t,int v,int c=INF)
{ ins(u,t,v,c);ins(t,u,-v,0); }

bool SPFA()
{
    memset(dis,0x3f,sizeof(dis));
    queue<int> q;
    q.push(S);
    dis[S]=0;
    prev[S]=-1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        int i=head[u];
        while(i)
        {
            if(e[i].cap && dis[u]+e[i].val<dis[e[i].to])
            {
                dis[e[i].to]=dis[u]+e[i].val;
                prev[e[i].to]=u;
                path[e[i].to]=i;
                q.push(e[i].to);
            }
            i=e[i].next;
        }
    }
    if(dis[T]==INF) return 0;
    return 1;
}

int argument()
{
    int w=INF,cost=0;
    for(int i=T;prev[i]!=-1;i=prev[i])
        w=min(w,e[path[i]].cap);
    for(int i=T;prev[i]!=-1;i=prev[i])
    {
        e[path[i]].cap-=w;
        e[path[i]^1].cap+=w;
        cost+=e[path[i]].val*w;
    }
    return cost;
}

int MCMF()
{
    int ans=0;
    while(SPFA()) ans+=argument();
    return ans;
}

void init()
{
    int s,t,c;
    n=read(),m=read(),S=0,T=n+2,cnt=1;
    for(int i=1;i<=n;++i) demond[i]=read();
    for(int i=1;i<=m;++i) s=read(),t=read(),c=read(),insert(s,t+1,c);
    for(int i=1;i<=n+1;++i)
    {
        c=demond[i]-demond[i-1];
        if(c>=0) insert(S,i,0,c);
        else insert(i,T,0,-c);
        if(i>1) insert(i,i-1,0);
    }
}

int main()
{
    init();
#ifdef DEBUG
    for(int i=1;i<=cnt;++i)
        printf("%d-->to=%d,next=%d,cap=%d,val=%d\n",i,e[i].to,e[i].next,e[i].cap,e[i].val);
#endif
    printf("%d\n",MCMF());
    return 0;
} 

扫描二维码,在手机上阅读!
Responses