Bakser's Blog

我是逗比。

bzoj1221 费用流

| Comments

这题比较经典,原题就是24题里的餐巾计划
每一天拆成两个点Xi(可以理解为接受新的餐巾),Yi(可以理解为洗脏毛巾)。
然后对于题目中给的条件分别建边
1.可以买餐巾,建边s->Xi,费用为f。
2.用过的餐巾可以不洗扔掉,建边Xi->t,容量ni,费用0(同时限制了每天必须用足够的餐巾)
3.可以洗餐巾,s->Yi,ni,0.
4.可以选择a方式和b方式(同时今天的餐巾是明天洗),所以建边Yi->Xi+a+1:INF:fa和Yi->Xi+b+1:INF:fb
5.今天的餐巾可以留到明天洗:Yi->Yi+1 INF 0

bzoj1221
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define N 3200
#define INF 0x7f7f7f7f
#define MIN(a,b) (((a)<(b))?(a):(b))
struct hh
{
    int next,u,v,cap,cost;
}edges[N<<5];
int n,a,b,f,fa,fb,s,t,point[N],cost,dis[N],p[N];
bool in[N];
queue<int> q;
inline void addedge(int u,int v,int cap,int cost)
{
    static int en(-1);
    edges[++en].next=point[u];edges[en].u=u;edges[en].v=v;edges[en].cap=cap;edges[en].cost=cost;point[u]=en;
    edges[++en].next=point[v];edges[en].u=v;edges[en].v=u;edges[en].cap=0;edges[en].cost=-cost;point[v]=en;
}
inline bool spfa()
{
    memset(dis,0x7f,sizeof(dis));
    dis[s]=0;q.push(s);in[s]=1;
    while(!q.empty())
    {
        int x(q.front());q.pop();in[x]=0;
        for(int i(point[x]);i!=-1;i=edges[i].next)
            if(edges[i].cap&&dis[x]+edges[i].cost<dis[edges[i].v])
            {
                dis[edges[i].v]=dis[x]+edges[i].cost;
                p[edges[i].v]=i;
                if(!in[edges[i].v])q.push(edges[i].v),in[edges[i].v]=1;
            }
    }
    return dis[t]<INF;
}
inline int augment()
{
    int flow(INF);
    for(int x(t);x!=s;x=edges[p[x]].u)
        flow=MIN(edges[p[x]].cap,flow);
    for(int x(t);x!=s;x=edges[p[x]].u)
        edges[p[x]].cap-=flow,edges[p[x]^1].cap+=flow;
    return flow;
}
int main()
{
    scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fa,&fb);
    s=0;t=(n<<1^1)+1;
    memset(point,0xff,sizeof(point));
    for(int i(1),tmp;i<=n;i++)
    {
        scanf("%d",&tmp);
        addedge(s,i<<1,tmp,f);
        addedge(i<<1,t,tmp,0);
        addedge(s,i<<1^1,tmp,0);
        if(i<n)addedge(i<<1^1,(i+1)<<1^1,INF,0);
        if(i+a+1<=n)addedge(i<<1^1,(i+a+1)<<1,INF,fa);
        if(i+b+1<=n)addedge(i<<1^1,(i+b+1)<<1,INF,fb);
    }
    int hh;
    while(spfa())
        cost+=augment()*dis[t];
    printf("%d\n",cost);
    return 0;
}

Comments

comments powered by Disqus