首页 > 其他 > 详细

[NOI2008]志愿者招募(网络流)

时间:2020-05-13 09:52:51      阅读:62      评论:0      收藏:0      [点我收藏+]

[NOI2008]志愿者招募

Solution

把志愿者想象成积木,那么就是在一条数轴上每个位置搭上特定高度的积木

那么也可以转化成在数轴上每个位置挖特定深度的坑,最后填平,志愿者是土

先把坑挖好,add(i,i+1,inf-a[i],0)

然后填坑只能用土,add(s[i],t[i]+1,inf,c[i])

跑最小费用最大流

Code

 

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e4+10,M=4e4;
int mc,mf,n,m,s,t,a[N],l[N],r[N],c[N],inf=1<<30;
int head[N],ver[M],nxt[M],edge[M],cost[M],tot=1;
void add(int u,int v,int w,int c)
{
    ver[++tot]=v,nxt[tot]=head[u],edge[tot]=w,cost[tot]=c,head[u]=tot;
    ver[++tot]=u,nxt[tot]=head[v],edge[tot]=0,cost[tot]=-c,head[v]=tot;
}
int incf[N],pre[N],dis[N],in[N];
bool spfa()
{
    memset(dis,0x3f,sizeof(dis));
    queue <int> q;
    dis[s]=0,pre[t]=-1,incf[s]=inf;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        in[u]=0;
        for(int i=head[u],v;i;i=nxt[i])
            if(edge[i]>0 && dis[v=ver[i]]>dis[u]+cost[i])
            {
                dis[v]=dis[u]+cost[i];
                pre[v]=i,incf[v]=min(incf[u],edge[i]);
                if(!in[v]) in[v]=1,q.push(v);
            }
    }
    return pre[t]!=-1;
}
void update()
{
    mf+=incf[t],mc+=incf[t]*dis[t];
    int x=t;
    while(x!=s)
    {
        int i=pre[x];
        edge[i]-=incf[t],edge[i^1]+=incf[t];
        x=ver[i^1];
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    s=0,t=n+1;
    add(s,1,inf,0);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),add(i,i+1,inf-a[i],0);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&l[i],&r[i],&c[i]);
        add(l[i],r[i]+1,inf,c[i]);
    }
    while(spfa()) update();
    printf("%d\n",mc);
    return 0;
}

 

 

 

[NOI2008]志愿者招募(网络流)

原文:https://www.cnblogs.com/hsez-cyx/p/12880084.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!