[BZOJ1061/Luogu3980][Noi2008]志愿者招募(网络流,单纯型)

发布于 2018-02-11  61 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1061/Luogu3980][Noi2008]志愿者招募(网络流,单纯型)

Description

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

Http

BZOJ
Luogu

Tag

网络流,单纯型

解决思路

又是一道网络流神题。先看一个例子
假设总共\(5\)天,有四类志愿者,分别是\(1-2,1-5,2-4,3-5\),设\(P[i]\)表示第\(i\)天需要的人数,\(P[i]'\)表示第\(i\)天实际的人数,\(X[i]\)表示第\(i\)类志愿者的人数,则有下列不等式组
\[P[1]'=X[1]+X[2]>=P[1] \\ P[2]'=X[1]+X[2]+X[3]>=P[2] \\ P[3]'=X[2]+X[3]+X[4]>=P[3] \\ P[4]'=X[2]+X[3]+X[4]>=P[4] \\ P[5]'=X[2]+X[4]>=P[5]\]
对每一个式子补充一个\(Y[i]\)把不等式变成等式
\[P[1]'=X[1]+X[2]-Y[1]=P[1] \\ P[2]'=X[1]+X[2]+X[3]-Y[2]=P[2] \\ P[3]'=X[2]+X[3]+X[4]-Y[3]=P[3] \\ P[4]'=X[2]+X[3]+X[4]-Y[4]=P[4] \\ P[5]'=X[2]+X[4]-Y[5]=P[5]\]
设有\(P[0]=P[6]=0\),相邻两式相减,得到
\[P[1]'-P[0]'=X[1]+X[2]-Y[1]=P[1] \\ P[2]'-P[1]'=X[3]-Y[2]+Y[1]=P[2]-P[1] \\ P[3]'-P[2]'=X[4]-Y[3]-X[1]+Y[2]=P[3]-P[2] \\ P[4]'-P[3]'=-Y[4]+Y[3]=P[4]-P[3] \\ P[5]'-P[4]'=-Y[5]-X[3]+Y[4]=P[5]-P[4] \\ P[6]'-P[5]'=-X[2]-X[4]+Y[5]=-P[5] \]
发现,每一个\(X[i]\)和每一个\(Y[i]\)都在这些式子中恰好出现了一次。并且这些式子的和为\(0\),这里有没有想到与网络流的流量平衡有一些关系?
把左边去掉,留下中间的和右边的,移项得到
\[P[1]-X[1]-X[2]+Y[1]=0 \\ P[2]-P[1]-X[3]+Y[2]-Y[1]=0 \\ P[3]-P[2]-X[4]+Y[3]+X[1]-Y[2]=0 \\ P[4]-P[3]+Y[4]-Y[3]=0 \\ P[5]-P[4]+Y[5]+X[3]-Y[4]=0 \\ P[6]-P[5]+X[2]+X[4]-Y[5]=0\]
这样,把每一个等式看作一个点,前面符号为\(+\)的为流入的流量,符号为\(-\)的为流出的流量,当出入平衡时,这个方程组就有解。而\(P[i]-P[i-1]\)的常数项就相当于与源汇点连的边,这个值为正则是从源点流出来的,否则则是流向汇点的。
观察到对于一类可以从第\(i\)天到第\(j\)天的志愿者,他对应的\(X[]\)在第\(i\)个等式中为负,在第\(j+1\)个等式中为正,那么就从\(i\)到\(j+1\)连一条容量为无穷大费用为志愿者费用的边。对于\(Y[i]\)则同理,只是此时是没有费用的。建完图后跑最小费用流即可。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=1010;
const int maxM=(10100+maxN*2)*2;
const int maxQueue=maxN*10;
const int inf=2147483647;
const ll INF=1e15;

class Edge
{
public:
    ll u,v,flow,w;
};

int n,m,S,T;
int Pl[maxN];
int edgecnt=-1,Head[maxN],Next[maxM];
Edge E[maxM];
ll Dist[maxN],inqueue[maxN],Queue[maxQueue];
ll Flow[maxN],Path[maxN];

void Add_Edge(int u,int v,int flow,int w);
bool spfa();

int main()
{
    mem(Head,-1);
    scanf("%d%d",&n,&m);S=n+2;T=n+3;
    for (int i=1;i<=n;i++) scanf("%d",&Pl[i]);
    for (int i=1;i<=m;i++)
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        Add_Edge(u,v+1,inf,w);//对于每一类志愿者分别连边
    }
    for (int i=1;i<=n+1;i++)
    {
        int p=Pl[i]-Pl[i-1];//对于常数项,讨论正负性分别与源汇点连边
        if (p>=0) Add_Edge(S,i,p,0);
        if (p<0) Add_Edge(i,T,-p,0);
        if (i>1) Add_Edge(i,i-1,inf,0);//这里连Y的边
    }
    ll Ans=0;
    while (spfa())
    {
        Ans=Ans+Dist[T]*Flow[T];
        int now=T;
        while (now!=S)
        {
            E[Path[now]].flow-=Flow[T];
            E[Path[now]^1].flow+=Flow[T];
            now=E[Path[now]].u;
        }
    }
    printf("%lld\n",Ans);
    return 0;
}

void Add_Edge(int u,int v,int flow,int w)
{
    //cout<<"Add:"<<u<<" "<<v<<" "<<flow<<" "<<w<<endl;
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;E[edgecnt].u=u;E[edgecnt].v=v;E[edgecnt].w=w;E[edgecnt].flow=flow;
    edgecnt++;Next[edgecnt]=Head[v];Head[v]=edgecnt;E[edgecnt].u=v;E[edgecnt].v=u;E[edgecnt].w=-w;E[edgecnt].flow=0;
    return;
}

bool spfa()
{
    mem(inqueue,0);
    for (int i=1;i<=T;i++) Dist[i]=INF;
    int h=1,t=0;Queue[1]=S;Dist[S]=0;inqueue[S]=1;Flow[S]=inf;
    do
    {
        t++;if (t>=maxQueue) t=0;
        int u=Queue[t];
        //cout<<"u:"<<u<<endl;
        for (int i=Head[u];i!=-1;i=Next[i])
        {
            //cout<<u<<" "<<E[i].v<<" "<<E[i].flow<<" "<<E[i].w<<endl;
            if ((E[i].flow>0)&&(Dist[E[i].v]>Dist[u]+E[i].w))
            {
                Dist[E[i].v]=Dist[u]+E[i].w;
                Path[E[i].v]=i;Flow[E[i].v]=min(Flow[u],E[i].flow);
                if (inqueue[E[i].v]==0)
                {
                    h++;if (h>=maxQueue) h=0;
                    inqueue[Queue[h]=E[i].v]=1;
                }
            }
        }
        inqueue[u]=0;
    }
    while (t!=h);
    //for (int i=1;i<=T;i++) cout<<Dist[i]<<" ";cout<<endl;
    if (Dist[T]==INF) return 0;
    return 1;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ1061/Luogu3980][Noi2008]志愿者招募(网络流,单纯型)


HNCJ OIer 一枚