最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

NOI 2008 志愿者招募 题解 (神奇费用流)

来源：博客园


【资料图】

洛谷题目链接

思路很清奇的网络流题

这种第i天需要至少\(a_i\)人的限制，按常规思路容易想到在i号点和i+1号点之间连一条容量为\(a_i\)的边，并强制流满。但是如果雇佣了一个人，他只能从\(s_i天工作到t_i\)天，我们无法控制他只流这个区间内的边，所以需要换一种思路。

考虑如下建图。对于第i天的限制，我们从第i个点到第i+1个点连一条边，费用为0，先不管它的容量是多少，反正这条边代表第i天的限制。然后对于第i类人，从第\(s_i\)个点到第\(t_i+1\)个点连容量为inf，费用为\(c_i\)的边，这条边的最终流量就代表招募的这种人的个数。然后从源点到第1个点连容量为inf费用为0的边，从第n+1个点到汇点也连一样的边。其实这个图跑最小费用最大流的最终费用就是答案(第一类边的容量接下来说明)，考虑证明。

令这个图的最大流量为tot。由于这个图是一个dag，根据网络流的性质，在取最小费用最大流时，对任意i，第\(i(1\le i \le n)\)个点到第\(i+1\)个点的所有边(包括直接相连的边以及跨过i和i+1中间这个空档的志愿者边)的总流量是tot。我们希望对于任意i，跨过i和i+1之间的空档的志愿者边的流量总和\(\ge a_i\)，这等价于i和i+1之间直接相连的那条边的流量\(\le tot-a_i\)。如果我们令每条\(i\to i+1\)的边的容量为\(inf-a_i\)(注意这题中提到的inf都不是无穷，而是一个很大的数比如1e16)，其实这个图的最大流量就是inf(这个待会证明)，也就是tot=inf，且此时显然每条\(i\to i+1\)的边流量都不超过\(tot-a_i\)，所以在这个情况下求出的最小费用最大流的费用就是答案。

然后来证明这个图的最大流是inf。首先由于源点到1号点的容量就是inf，所以最大流不会超过inf。由于题目保证有解，那么假设我们随意取出一组解(不需要费用最小)，并按照这个解先分配好每条志愿者边的流量。然后强制这个图的总流量是inf，然后从左往右推，该由志愿者边分流的时候就分流，其余的直接沿着\(i\to i+1\)的边往前流，发现永远不会发生边容量不够的情况，所以最大流\(\ge inf\)。综上，最大流量就是inf。

点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define pb push_back#define mpr make_pairvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;struct edge{LL to,flow,cost,rev;edge(LL a,LL b,LL c,LL d):to(a),flow(b),cost(c),rev(d){}};namespace minCostFlow{vector  g[10010];LL n,dist[10010],cur[10010];  bool inq[10010],vis[10010];queue  q;void add_edge(LL x,LL y,LL flow,LL cost){g[x].pb(edge(y,flow,cost,(LL)g[y].size()));g[y].pb(edge(x,0,-cost,(LL)g[x].size()-1));}  bool relax(LL to,LL fr,LL e)  {    if(dist[to]>dist[fr]+e)    {      dist[to]=dist[fr]+e;      return true;    }    return false;  }  bool spfa(LL s,LL t)  {    rep(i,n+3) dist[i]=1e18;    dist[s]=0;inq[s]=true;q.push(s);    while(!q.empty())    {      LL p=q.front();q.pop();inq[p]=false;      rep(i,g[p].size()) if(g[p][i].flow>0)      {        if(relax(g[p][i].to,p,g[p][i].cost)&& !inq[g[p][i].to])        {          inq[g[p][i].to]=true;          q.push(g[p][i].to);        }      }    }    return dist[t]<1e18;  }  pii dfs(LL pos,LL t,LL fl)  {    if(pos==t) return mpr(fl,0);    vis[pos]=true;    for(LL i=cur[pos];i0&&dist[g[pos][i].to]==dist[pos]+g[pos][i].cost)    {      pii res=dfs(g[pos][i].to,t,min(fl,g[pos][i].flow));      if(res.fi>0)      {        res.se+=g[pos][i].cost*res.fi;        g[pos][i].flow-=res.fi;g[g[pos][i].to][g[pos][i].rev].flow+=res.fi;        vis[pos]=false;        return res;      }    }    vis[pos]=false;    return mpr(0,0);  }  pii mcmf(LL s,LL t)  {    pii ret=mpr(0,0);    while(spfa(s,t))    {      rep(i,n+3) cur[i]=0;      while(true)      {        pii val=dfs(s,t,1e18);        if(val.fi==0) break;        ret.fi+=val.fi;ret.se+=val.se;      }    }    return ret;  }}LL n,m,a[1010];int main(){  fileio();  cin>>n>>m;  repn(i,n) scanf("%lld",&a[i]);  LL ss=n+2,tt=n+3,inf=1e16;  minCostFlow::add_edge(ss,1,inf,0);minCostFlow::add_edge(n+1,tt,inf,0);  repn(i,n) minCostFlow::add_edge(i,i+1,inf-a[i],0);  rep(i,m)  {    LL x,y,z;    scanf("%lld%lld%lld",&x,&y,&z);    minCostFlow::add_edge(x,y+1,inf,z);  }  minCostFlow::n=n+3;  cout<

关键词：