大发体育娱乐在线-大发体育娱乐官方网站-大发体育娱乐登录网址
做最好的网站

志愿者招募

来源:http://www.dfwstonefabricators.com 作者:编程应用 人气:79 发布时间:2019-09-24
摘要:Time Limit:20 SecMemory Limit:162 MB Submit:5725Solved:3437 [Submit][Status][Discuss] Description   申奥成功后,布布经过不懈努力,终于成为奥组织委员会委员下属公司人力能源部门的总经理。布布刚上任

Time Limit:20 SecMemory Limit:162 MB
Submit:5725Solved:3437
[Submit][Status][Discuss]

Description

 

  申奥成功后,布布经过不懈努力,终于成为奥组织委员会委员下属公司人力能源部门的总经理。布布刚上任就境遇了多少个难

题:为就要开发银行的奥运新类型招募一群长时间志愿者。经过揣测,这一个项目需求N 天本事不辱任务,在那之中第i 天至少须要

Ai 个人。 布布通过领悟得知,一共有M 类志愿者能够招募。在那之中第i 类能够从第Si 天专门的职业到第Ti 天,招募成本

是每位Ci 元。新官上任三把火,为了理想地产生自个儿的办事,布布希望用尽量少的花销招募足够的志愿者,但那

并不是他的拿手好戏!于是布布找到了你,希望你帮她安插一种最优的招生方案。

Description

  申办奥运会成功后,布布经过不懈努力,终于成为奥组织委员会委员下属公司人力能源部门的掌管。布布刚上任就碰见了贰个难点:为将要开发银行的奥林匹克运动新品类招募一堆短时间志愿者。经过估摸,那些种类供给N 天能力到位,在那之中第i 天至少需求Ai 个人。 布布通过精通得知,一共有M 类义工能够招募。个中第i 类能够从第Si 天做事到第Ti 天,招募花费是每位Ci 元。新官上任三把火,为了特出地产生本人的办事,布布希望用尽量少的开支招募丰裕的志愿者,但那而不是她的一艺之长!于是布布找到了您,希望您帮他设计一种最优的招生方案。

Input

  第一行包涵多个整数N, M,表示完毕项指标造化和能够招募的志愿者的类型。 接下来的一行中包罗N 个非负

大背头,表示每日最少需求的志愿者人数。 接下来的M 行中每行满含八个整数Si, Ti, Ci,含义如上文所述。为了

便利起见,大家得以以为每类志愿者的数码都以无比多的。

Input

  第一行满含七个整数N, M,表示完结项指标运气和能够招募的志愿者的类型。 接下来的一行中含有N 个非负整数,表示每日最少要求的志愿者人数。 接下来的M 行中每行富含多个整数Si, Ti, Ci,含义如上文所述。为了方便起见,大家得以感到每类志愿者的数目都以Infiniti多的。

Output

  仅满含贰个整数,表示您所设计的最优方案的总成本。

Output

  仅包涵一个整数,表示您所设计的最优方案的总开销。

Sample Input

3 3
2 3 4
1 2 2
2 3 5
3 3 2

Sample Input

3 3
2 3 4
1 2 2
2 3 5
3 3 2

Sample Output

14

Sample Output

14

HINT

1 ≤ N ≤ 一千,1 ≤ M ≤ 一千0,标题中其余所涉嫌的数量均 不超过2^31-1。

HINT

1 ≤ N ≤ 1000,1 ≤ M ≤ 10000,题目中任何所涉嫌的多寡均 不超越2^31-1。

题解

难题中的式子有一些多,大家把它们都写出来:

令第$i$天的总志愿者人数为$P_i$,第$j$种志愿者征集人数为$K_j$,那么有

$$P_i = P_{i-1} + sum_{S_j=i}K_j - sum_{T_j=i-1}K_j geq A_i$$

$P_i geq A_i$不太好管理,大家把它写成

$$P_i = A_i + B_i (B_i geq 0)$$

那便是说大家就有

$$P_i - P_{i-1} = sum_{S_j=i}K_j - sum_{T_j=i-1}K_j = A_i + B_i - A_{i-1} - B_{i-1}$$

$$sum_{S_j=i}K_j + B_{i-1} + A_{i-1} =  sum_{T_j=i-1}K_j + B_i + A_i$$

咱俩发掘,每一个义工所表示的$K_j$只在$S_j$和$T_j+1$五个姿态里涌出,并且一左一右,每一天的松散变量$B_i$也只在$i$和$i+1$出现,且一左一右。

何况以此姿势很像网络流中的流量平衡:

$$out_i = in_i$$

其中$in_i, out_i$分别是有个别点的流入和流出。

这里,

$$in_i = sum_{T_j=i-1}K_j + B_i + A_i$$

$$out_i = sum_{S_j=i}K_i + B_{i-1} + A_{i-1}$$

由于$A_i,A_{i-1}$是必得满意的,所以大家将其视为i与S,T之间的边容积,并且叁个点既从S流入又向T流出未有意义,我们只需保留体量相当的大的边,容量为$|A_i-A_{i-1}|$。

那正是说,今后有$n+3$个点,即起点,汇点,第一天到第$n+1$天的点(若未有第$n+1$天,那么一些$K_j$不会出现四回),边有三种:

1.$K_j$对应的边,由$S_j$连向$T_j+1$,单位代价$C_j$,容量$infty$。

2.$B_i$对应的边,由$i+1$连向$i$,单位代价$0$,体积$infty$。

3.$A_i-A_{i-1}$对应的边,由$S$连向$i$或由$i$连向$T$,单位代价$0$,容积$|A_i-A_{i-1}|$。

最终求三次最小开支最大流,则每条项目为1的边流量即为此种志愿者征集个数,种类为2的边流量即为该天比须求多多少,类别为3的边均满流(不然无解)。

出口成本就能够。

附代码:

#include <algorithm>
#include <cstdio>
#include <queue>
using std::queue;
typedef long long LL;
const LL INF = 10000000000000000;
const int N = 1050;
const int M = 100050;
struct MCMF{
  int to[M];
  LL cost[M], ret[M];
  int pre[N], nxt[M], cnt;
  LL dis[N];
  int las[N];
  bool inQ[N];
  queue<int> Q;
  MCMF() {
    std::fill(pre, pre + N, -1);
    cnt = 0;
  }
  inline void addEdge(int u, int v, LL w, LL c) {
    to[cnt] = v, cost[cnt] = w, ret[cnt] = c;
    nxt[cnt] = pre[u], pre[u] = cnt++;
    to[cnt] = u, cost[cnt] = -w, ret[cnt] = 0;
    nxt[cnt] = pre[v], pre[v] = cnt++;
  }
  bool SPFA(int s, int t) {
    std::fill(dis, dis + N, INF);
    std::fill(inQ, inQ + N, 0);
    dis[s] = 0;
    inQ[s] = true;
    while (!Q.empty()) Q.pop();
    Q.push(s);
    while (!Q.empty()) {
      int x = Q.front(); Q.pop();
      inQ[x] = false;
      for (int i = pre[x]; ~i; i = nxt[i]) if (ret[i]) {
        int v = to[i];
        if (dis[v] > dis[x] + cost[i]) {
          dis[v] = dis[x] + cost[i];
          las[v] = i;
          if (!inQ[v]) {
            inQ[v] = true;
            Q.push(v);
          }
        }
      }
    }
    return dis[t] < INF;
  }
  LL solve(int s, int t) {
    LL ans = 0;
    while (SPFA(s, t)) {
      LL p = INF;
      for (int i = t; i != s; i = to[las[i] ^ 1])
        p = std::min(p, ret[las[i]]);
      ans += p * dis[t];
      for (int i = t; i != s; i = to[las[i] ^ 1]) {
        ret[las[i]] -= p;
        ret[las[i] ^ 1] += p;
      }
    }
    return ans;
  }
};
MCMF solver;
int A[N];
int main() {
  int n, m, a, b, c;
  scanf("%d%d", &n, &m);
  int S = 0, T = n + 2;
  for (int i = 1; i <= n; ++i) scanf("%d", &A[i]);
  for (int i = 0; i < m; ++i) {
    scanf("%d%d%d", &a, &b, &c);
    solver.addEdge(a, b + 1, c, INF);
  }
  for (int i = 1; i <= n + 1; ++i) {
    int t = A[i] - A[i - 1];
    if (t >= 0) solver.addEdge(S, i, 0, t);
    else solver.addEdge(i, T, 0, -t);
    if (i > 1) solver.addEdge(i, i - 1, 0, INF);
  }
  printf("%lldn", solver.solve(S, T));
  return 0;
}

  

Source

一经不领会那题是线性规划的话确定很丢脸出来,然则知情了就好做多了

若$C_i$为第$i$个人的开销,$a_i$为第$i$天需求的人,$x_i$为第$i$个人的多寡

那么我们须求满意对于天天$i$,$sum_{i = 1}^{M} x_i >= a_i$,同时$sum C_i x_i$最小

什么?最小?当时自个儿生产式子来就蒙了qwq。然后跑去膜题解

依赖对偶原理,难点相当于使得$sum_{i = 1}^{M} x_i <= C_i$,的情状下$sum a_i x_i$最大

周详一想左近挺有道理

有关最后答案是还是不是为整数的标题

#include<cstdio>#include<algorithm>#include<cmath>#define LL long long using namespace std;const int MAXN = 51, INF = 1e9 + 10;const double eps = 1e-8;inline int read() {    char c = getchar();int x = 0,f = 1;    while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}    while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();}    return x * f;}int N, M;LL a[10001][1001];void Pivot(int l, int e) {    double t = a[l][e]; a[l][e] = 1;    for(int i = 0; i <= N; i++) a[l][i] /= t;    for(int i = 0; i <= M; i++) {        if(i != l && abs > eps) {            t = a[i][e]; a[i][e] = 0;            for(int j = 0; j <= N; j++)                a[i][j] -= a[l][j] * t;        }    }}bool simplex() {    while(1) {        int l = 0, e = 0; double mn = INF;        for(int i = 1; i <= N; i++)            if(a[0][i] > eps)                 {e = i; break;}        if break;        for(int i = 1; i <= M; i++)            if(a[i][e] > eps && a[i][0] / a[i][e] < mn)                mn = a[i][0] / a[i][e], l = i;        Pivot;    }    return 1;}int main() {    srand(19260817);    N = read(); M = read();    for(int i = 1; i <= N; i++) a[0][i] = read();        for(int i = 1; i <= M; i++) {         int S = read(), T = read(), C = read();        for(int j = S; j <= T; j++)                a[i][j] = 1;        a[i][0] = C;    }    simplex();    printf("%lld", -a[0][0]);    return 0;}

本文由大发体育娱乐在线发布于编程应用,转载请注明出处:志愿者招募

关键词:

上一篇:放置模块re,正则表明式4位数字

下一篇:没有了

最火资讯