【网络流】【BZOJ1221】【HNOI2001】软件开发

原题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1221

题意：你有3种方法进行对毛巾的处理，不同的处理方法有不同的cost，问你要如何规划才可以使得总花费最低。

解题思路：我们对每个点进行拆点，分为用过的毛巾和没用过的，这样就可以较为简单的连边，然后跑个最小费用最大流即可。

AC代码：

#include<stdio.h>

#include<string.h>

#define inf 0x7fffffff

#define min(a,b) (a<b?a:b)

struct zxy{int to,next,c,v;}edge[];

int n,e,cnt=,head[],dis[],que[],pre[],fc,ta,tb,fa,fb;

bool vis[];

inline int in(){

    int x=;

    char ch=getchar();

    while(ch<''||ch>'') ch=getchar();

    while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x;

}

inline void ins(int x,int y,int v,int l){

    edge[++cnt].to=y,edge[cnt].next=head[x],edge[cnt].v=v,edge[cnt].c=l,head[x]=cnt;

    edge[++cnt].to=x,edge[cnt].next=head[y],edge[cnt].v=,edge[cnt].c=l*(-),head[y]=cnt;

}

inline bool SPFA(int s,int e){

    for (register int i=s; i<=e; ++i) dis[i]=inf/;

    int h=,t=;

    que[]=s;

    dis[s]=;vis[s]=;

    do{

        int w=que[++h];

        for (register int i=head[w]; i; i=edge[i].next)

            if (dis[w]+edge[i].c<dis[edge[i].to]&&edge[i].v){

                int v=edge[i].to;pre[v]=i;

                dis[v]=dis[w]+edge[i].c;

                if (!vis[v]){

                    vis[v]=;

                    if (dis[v]<dis[que[h+]])que[h--]=v;

                    else que[++t]=v;

                }

            }

        vis[w]=;

    }while(h<t);

    return dis[e]!=inf/;

}

int cost_flow(int s,int t){

    int cost=;

    while(SPFA(s,t)){

        int mi=inf;

        for (register int i=t; i; i=edge[pre[i]^].to)

            mi=min(mi,edge[pre[i]].v);

        for (register int i=t; i; i=edge[pre[i]^].to)

            edge[pre[i]].v-=mi,edge[pre[i]^].v+=mi;

        cost+=dis[t]*mi;

    }

    return cost;

}

void init(){

    n=in(),ta=in(),tb=in(),fc=in(),fa=in(),fb=in();

    for (int i=; i<=n; ++i){

        register int x=in();

        ins(,n+i,inf,fc);

        ins(,i,x,);

        ins(n+i,*n+,x,);

        if(i<n) ins(i,i+,inf,);

        if(i+ta<n) ins(i,i+ta+n+,inf,fa);

        if(i+tb<n) ins(i,i+tb+n+,inf,fb);

    }

}

int main(){

    init();

    printf("%d",cost_flow(,*n+));

}