【费用流】bzoj1221 [HNOI2001] 软件开发

矫情吗；* 2022-01-07 01:21 155阅读 0赞

几乎为“线性规划与网络流24题”中的餐巾问题。

这里把S看成毛巾的来源，T看成软件公司，我们的目的就是让每天的毛巾满足要求(边满流)。

引用题解：

*【问题分析】*

*网络优化问题，用最小费用最大流解决。*

*【建模方法】*

*把每天分为二分图两个集合中的顶点Xi,Yi，建立附加源S汇T。*

*1、从S向每个Xi连一条容量为ri，费用为0的有向边。*  
*2、从每个Yi向T连一条容量为ri，费用为0的有向边。*  
*3、从S向每个Yi连一条容量为无穷大，费用为p的有向边。*  
*4、从每个Xi向Xi+1(i+1<=N)连一条容量为无穷大，费用为0的有向边。*  
*5、从每个Xi向Yi+m+1(i+m+1<=N)连一条容量为无穷大，费用为f的有向边。*  
*6、从每个Xi向Yi+n+1(i+n+1<=N)连一条容量为无穷大，费用为s的有向边。*

*求网络最小费用最大流，费用流值就是要求的最小总花费。*

*【建模分析】*

*这个问题的主要约束条件是每天的餐巾够用，而餐巾的来源可能是最新购买，也可能是前几天送洗，今天刚刚洗好的餐巾。每天用完的餐巾可以选择送到快洗部或慢洗部，或者留到下一天再处理。*

*经过分析可以把每天要用的和用完的分离开处理，建模后就是二分图。二分图X集合中顶点Xi表示第i天用完的餐巾，其数量为ri，所以从S向Xi连接容量为ri的边作为限制。Y集合中每个点Yi则是第i天需要的餐巾，数量为ri，与T连接的边容量作为限制。每天用完的餐巾可以选择留到下一天（Xi->Xi+1），不需要花费，送到快洗部(Xi->Yi+m+1)，费用为f，送到慢洗部(Xi->Yi+n+1)，费用为s。每天需要的餐巾除了刚刚洗好的餐巾，还可能是新购买的(S->Yi)，费用为p。*

*在网络上求出的最小费用最大流，满足了问题的约束条件（因为在这个图上最大流一定可以使与T连接的边全部满流，其他边只要有可行流就满足条件），而且还可以保证总费用最小，就是我们的优化目标。*

#include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<queue>
    using namespace std;
    #define MAXN 2011
    #define MAXM 150011
    #define INF 2147483647
    int S,T,n;
    int en,u[MAXM],v[MAXM],first[MAXN],next[MAXM],cap[MAXM],cost[MAXM];//Next Array
    bool inq[MAXN];
    int d[MAXN]/*spfa*/,p[MAXN]/*spfa*/,a[MAXN]/*可改进量*/;
    int C,WA,WB,CA,CB,X;
    queue<int>q;
    void Init_MCMF(){memset(first,-1,sizeof(first));en=0;S=0;T=(n<<1|1);}
    void AddEdge(const int &U,const int &V,const int &W,const int &C)
    {u[en]=U; v[en]=V; cap[en]=W; cost[en]=C; next[en]=first[U]; first[U]=en++;
    u[en]=V; v[en]=U; cost[en]=-C; next[en]=first[V]; first[V]=en++;}
    bool Spfa(int &Flow,int &Cost)
    {
        memset(d,0x7f,sizeof(d));
        memset(inq,0,sizeof(inq));
        d[S]=0; inq[S]=1; p[S]=0; a[S]=INF; q.push(S);
        while(!q.empty())
          {
            int U=q.front(); q.pop(); inq[U]=0;
            for(int i=first[U];i!=-1;i=next[i])
              if(cap[i] && d[v[i]]>d[U]+cost[i])
                {
                  d[v[i]]=d[U]+cost[i];
                  p[v[i]]=i;
                  a[v[i]]=min(a[U],cap[i]);
                  if(!inq[v[i]]) {q.push(v[i]); inq[v[i]]=1;}
                }
          }
        if(d[T]>2100000000) return 0;
        Flow+=a[T]; Cost+=d[T]*a[T]; int U=T;
        while(U!=S)
          {
            cap[p[U]]-=a[T]; cap[p[U]^1]+=a[T];
            U=u[p[U]];
          }
        return 1;
    }
    int Mincost()
    {
        int Flow=0,Cost=0;
        while(Spfa(Flow,Cost));
        return Cost;
    }
    int main()
    {
    	scanf("%d%d%d%d%d%d",&n,&WA,&WB,&C,&CA,&CB);
    	Init_MCMF();
    	for(int i=1;i<=n;++i)
    	  {
    	  	scanf("%d",&X);
    	  	AddEdge(S,i,X,0);
    	    AddEdge(i+n,T,X,0);
    	    AddEdge(S,i+n,INF,C);
    	    if(i+1<=n) AddEdge(i,i+1,INF,0);
    	    if(i+WA+1<=n) AddEdge(i,i+WA+1+n,INF,CA);
    	    if(i+WB+1<=n) AddEdge(i,i+WB+1+n,INF,CB);
    	  }
    	printf("%d\n",Mincost());
    	return 0;
    }

转载于:https://www.cnblogs.com/autsky-jadek/p/4174087.html