`

UVa11613 Acme Corporation 最小费用最大流模板

阅读更多

 

//题目给出T,表示测试组数。M和I表示要考虑的月数和单位的X每月要花费I元。
//再有M行的整数m,n,p,s,e。m表示第i月X的成产成本,n表示最大产量,p表示
//销售单价,s表示当月最大的销售量,e表示可以存储的月数,求最大利润。
//分析:
//    每月建立两个点,i1,i2.在建立一个源点(生产商),一个汇点(消费者)。
//原点到每个i1点表示第i月的产量,i2点到汇点表示第i月的销售量,i1到有效期
//内的每个i2表示产品的可以到在这几个月内卖掉,每条弧的容量和费用就不在赘述。

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;

const int maxn = 202 + 10;
const int INF = 1000000000;

typedef long long LL;

struct Edge {
  int from, to, cap, flow, cost;
};

struct MCMF {
  int n, m, s, t;
  vector<Edge> edges;
  vector<int> G[maxn];
  int inq[maxn];         // 是否在队列中
  int d[maxn];           // Bellman-Ford
  int p[maxn];           // 上一条弧
  int a[maxn];           // 可改进量

  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }

  void AddEdge(int from, int to, int cap, int cost) {
    edges.push_back((Edge){from, to, cap, 0, cost});
    edges.push_back((Edge){to, from, 0, 0, -cost});
    m = edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
  }

  bool BellmanFord(int s, int t, LL& ans) {
    for(int i = 0; i < n; i++) d[i] = INF;
    memset(inq, 0, sizeof(inq));
    d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF;

    queue<int> Q;
    Q.push(s);
    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      inq[u] = 0;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(e.cap > e.flow && d[e.to] > d[u] + e.cost) {
          d[e.to] = d[u] + e.cost;
          p[e.to] = G[u][i];
          a[e.to] = min(a[u], e.cap - e.flow);
          if(!inq[e.to]) { Q.push(e.to); inq[e.to] = 1; }
        }
      }
    }
    if(d[t] > 0) return false;
    ans += (LL)d[t] * (LL)a[t];
    int u = t;
    while(u != s) {
      edges[p[u]].flow += a[t];
      edges[p[u]^1].flow -= a[t];
      u = edges[p[u]].from;
    }
    return true;
  }

  // 需要保证初始网络中没有负权圈
  LL Mincost(int s, int t) {
    LL cost = 0;
    while(BellmanFord(s, t, cost));
    return cost;
  }

};

MCMF g;

int main() {
  int T, month, store_cost;
  scanf("%d", &T);
  for(int kase = 1; kase <= T; kase++) {
    scanf("%d%d", &month, &store_cost);
    g.init(2*month+2);//每一月看成两个点,再加一个源点一个汇点。
    int source = 0, sink = 2*month+1;//一个源点,一个汇点
    for(int i = 1; i <= month; i++) {
      int make_cost, make_limit, price, sell_limit, max_store;
      scanf("%d%d%d%d%d", &make_cost, &make_limit, &price, &sell_limit, &max_store);
      g.AddEdge(source, i, make_limit, make_cost);//算法求最小花费,可以看成是最小支出
      g.AddEdge(month+i, sink, sell_limit, -price); // 收益是负费用
      for(int j = 0; j <= max_store; j++) if(i + j <= month)
        g.AddEdge(i, month+i+j, INF, store_cost * j); // 存j个月以后卖
    }
    printf("Case %d: %lld\n", kase, -g.Mincost(source, sink));
  }
  return 0;
}

 

 

 

 

 

分享到:
评论

相关推荐

    Acme

    Acme

    ACME Bootstrap后台管理模版

    30美元买的ACME Bootstrap后台管理模版,值得参考

    ACME C/S风格

    ACME C/S风格 描述 ACME C/S风格 描述 ACME C/S风格 描述

    ACMEJava客户端ACME4j.zip

    ACME4j 是一个ACME(Automatic Certificate Management Environment )的客户端,采用Java编写。ACME是一个协议,通过ACME,证书颁发机构(CA)和申请人可以自动验证证书以及证书的发放。ACME4j通过连接到ACME服务器...

    acme 协议, 可以从 let‘s encrypt 生成免费的证书

    简单来说acme.sh 实现了 acme 协议, 可以从 let‘s encrypt 生成免费的证书。 acme.sh 有以下特点: 一个纯粹用Shell(Unix shell)语言编写的ACME协议客户端。 完整的ACME协议实施。 支持ACME v1和ACME v2 支持...

    Acme CAD Converter 2011

    Acme CAD Converter 2011

    2023年!使用acme为群晖NAS自动部署证书

    使用acme为群晖NAS自动部署证书 之前一直是用的阿里云的免费证书,只能单个域名申请,有效期一年。这样每年都需要进行证书更新,最近真的是头秃了。在查阅不少资料后,发现使用acme可以快速满足需求。 acme.sh是一...

    AcmeCADConverter8.23含注册码

    AcmeCADConverter8.23含注册码

    威联通qnap使用acme自动更新证书 qnap-acme.sh

    配合neilepang/acme.sh容器,QTS 5.x可用脚本

    win-acme的腾讯域名脚本DNSPod.ps1

    用win-acme给windows服务器添加SSL(Let's Encrypt)证书的Powershell脚本 腾讯云,腾讯域名使用 win-acme acme.sh

    Amp-acme.zip

    Amp-acme.zip,基于amp并发框架的php异步acme库。,amp是php的一个非阻塞并发框架。它提供事件循环、承诺和流,作为异步编程的基础。

    acme-client, letsencrypt协议的ACME的ruby 客户端.zip

    acme-client, letsencrypt协议的ACME的ruby 客户端 Acme::Client acme-client 是 ruby 中 ACME 协议的客户端实现。你可以在go和中找到服务器插件的ACME参考实现( in ) 。ACME是项目的一部分,目的是为获取和更新流程...

    ACME越峰磁芯资料

    ACME-PRODUCT 越峰磁芯资料 开关电源常用资料

    qnap-acme.sh

    威联通QNAP自动续签更新SSL证书脚本(配合acme.sh使用),支持Let's Encrypt免费证书,支持域名泛解析证书,如:*.xx.com。

    win-acme 网站https 证书免费申请工具

    用于windows网站申请免费版的https证书服务,3个月有效到期后再次手动申请即可续期无需任何费用,操作简单便捷

    Acme 基本介绍

    Acme简介 基本介绍ADL语言中ACME工具 提供一种基本的开发工具 软件架构 软件建模中的一种比较实用的工具

    Acme CAD Converter 2018 v8.9.8.1473破解版本

    Acme CAD Converter 2018 v8.9.8.1473破解版本Acme CAD Converter 2018 v8.9.8.1473破解版本Acme CAD Converter 2018 v8.9.8.1473破解版本Acme CAD Converter 2018 v8.9.8.1473破解版本Acme CAD Converter 2018 v8.9...

    Acme CAD Converter 2013 v8.51简体中文+注册

    Acme CAD Converter是一款强力的 CAD 文件处理工具,这是基于官方最新 8.1 版(2010-04-20)制作的简体中文版,软件已注册无任何功能和使用时间限制,不需要在帮助——注册中再次注册。主要功能如下: 可将 CAD ...

    AcmeCADConverter2017V8.8.6汉化

    AcmeCADConverter2017V8.8.6汉化,AcmeCADConverter8.8.6,AcmeCADConverter最新版,AcmeCADConverter绿色单文件

Global site tag (gtag.js) - Google Analytics