BZOJ1061-[Noi2008]志愿者招募
题意:
题解:
这题解法是费用流.第一眼我看到题解的时候,我想:这TM和费用流有啥关系!然后看完之后,我的内心:还有这种操作?
我们设第i个志愿者招x[i]个,则我们可以得到一组不等式:
sum(x[j])](s[j]<=j<=t[j])>=a[i];
然后添加进去几个变量:
sum(x[j])(s[j]<=i<=t[j])-y[i]==a[i]
显然,所有x和y都大于等于0.
我们将与a[i]有关的式子减去与a[i-1]有关的式子,得到:
sum(x[j])(s[j]<=i<=t[j])-sum(x[j])(s[j]<=i-1<=t[j])+y[i]-y[i-1]==a[i]-a[i-1]
如果一个x[j]在该式子中系数不为0,则意味着i-1在[s[j],t[j]]内且i不在[s[j],t[j]]内,或i-1不在[s[j],t[j]]内且i在[s[j],t[j]]内.对于第一种情况,i=t[j]+1且x[j]的系数为-1,对于第二种情况,i=s[j],且x[j]的系数为1.
那么对于所有x和y,它们都在这些式子都刚好出现了两次,并且一次系数为1,一次系数为-1.
然后,我们就(脑洞大开)地想到了网络流!我们把一个式子看成一个点,每个变量看成一条边,流量为inf,费用的话,如果是x,为代表的志愿者的费用,如果是y,为0.对于每一条变量代表的边,从它为正的式子连向它为负的式子.并且对于式子右边的常数(a[i]-a[i-1]),如果为正,从源点向该式子连一条容量为a[i]-a[i-1],费用为0的边,否则从该式子向汇点连一条容量为a[i-1]-a[i],费用为0的边,然后跑一遍费用流,就得到了答案,并且每条边的流量就是该变量的取值.
那么为什么这样是对的呢?这个建图法满足了网络流的一些性质.对于每条边,流量非负,而式子中所有变量都有非负限制.对于每个点,流入的流量等于流出的流量,而按照这种建图法,每个式子和其代表的点的限制其实是一样的.所以这样就是对的了.
#include<cstdio> #include<queue> #include<cstring> using namespace std; typedef long long ll; const int maxn=1000,maxm=10000; const ll inf=0x3f3f3f3f; struct edge{int to,nxt; ll cap,flow,val;}eg[maxm*4+10]; int h[maxn+10],ned[maxn+10],eg_cnt,n,m; void add_edge(int u,int v,int cap,int val){ eg[eg_cnt].to=v; eg[eg_cnt].cap=cap; eg[eg_cnt].val=val; eg[eg_cnt].nxt=h[u]; h[u]=eg_cnt++; } void add_edge_2(int u,int v,int cap,int val){ add_edge(u,v,cap,val); add_edge(v,u,0,-val); } ll a[maxn+10],flow[maxn+10],pre[maxn+10][2],d[maxn+10]; bool vis[maxn+10]; queue<int> Q; ll mcmf(){ ll ans=0; for(;;){ memset(flow,-1,sizeof flow); memset(d,0x3f,sizeof d); memset(vis,0,sizeof vis); d[1]=0; flow[1]=inf; vis[1]=1; Q.push(1); memset(pre,-1,sizeof pre); for(;!Q.empty();Q.pop()){ int x=Q.front(); vis[x]=0; for(int i=h[x];i!=-1;i=eg[i].nxt) if(eg[i].flow<eg[i].cap&&d[x]+eg[i].val<d[eg[i].to]){ d[eg[i].to]=d[x]+eg[i].val; flow[eg[i].to]=min(flow[x],eg[i].cap-eg[i].flow); pre[eg[i].to][0]=x; pre[eg[i].to][1]=i; if(!vis[eg[i].to]){ vis[eg[i].to]=1; Q.push(eg[i].to); } } } if(flow[2]==-1) break; ans+=flow[2]*d[2]; for(int i=2;pre[i][0]!=-1;i=pre[i][0]){ eg[pre[i][1]].flow+=flow[2]; eg[pre[i][1]^1].flow-=flow[2]; } } return ans; } int main(){ scanf("%d%d",&n,&m); memset(h,-1,sizeof h); for(int i=1;i<=n;++i) scanf("%lld",&a[i]); for(int i=1;i<=n+1;++i){ if(a[i]-a[i-1]>=0) add_edge_2(1,i+2,a[i]-a[i-1],0); else add_edge_2(i+2,2,a[i-1]-a[i],0); } for(int i=1;i<=m;++i){ int l,r,v; scanf("%d%d%d",&l,&r,&v); add_edge_2(l+2,r+3,inf,v); } for(int i=1;i<=n;++i) add_edge_2(i+3,i+2,inf,0); printf("%lld",mcmf()); }