BZOJ 1061: [Noi2008]志愿者招募 费用流

时间：2021-12-21 19:52:57

1061: [Noi2008]志愿者招募

题目连接：

http://www.lydsy.com/JudgeOnline/problem.php?id=1061

Description

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。

Input

第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负整数，表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。

Output

仅包含一个整数，表示你所设计的最优方案的总费用。

Sample Input

3 3

2 3 4

1 2 2

2 3 5

3 3 2

Sample Output

14

Hint

招募第一类志愿者3名，第三类志愿者4名 30%的数据中，1 ≤ N, M ≤ 10，1 ≤ Ai ≤ 10； 100%的数据中，1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均 不超过2^31-1。

题解：

单纯形裸题，费用流神题……

题解具体看：https://www.byvoid.com/blog/noi-2008-employee/

代码

#include<bits/stdc++.h>

using namespace std;

const int inf = 1e9;

const int MAXN = 10000;

const int MAXM = 100000;

const int INF = 0x3f3f3f3f;

struct Edge

{

    int to, next, cap, flow, cost;

    int x, y;

} edge[MAXM],HH[MAXN],MM[MAXN];

int head[MAXN],tol;

int pre[MAXN],dis[MAXN];

bool vis[MAXN];

int N, M;

char map[MAXN][MAXN];

void init()

{

    N = MAXN;

    tol = 0;

    memset(head, -1, sizeof(head));

}

void addedge(int u, int v, int cap, int cost)//左端点，右端点，容量，花费

{

    edge[tol]. to = v;

    edge[tol]. cap = cap;

    edge[tol]. cost = cost;

    edge[tol]. flow = 0;

    edge[tol]. next = head[u];

    head[u] = tol++;

    edge[tol]. to = u;

    edge[tol]. cap = 0;

    edge[tol]. cost = -cost;

    edge[tol]. flow = 0;

    edge[tol]. next = head[v];

    head[v] = tol++;

}

bool spfa(int s, int t)

{

    queue<int>q;

    for(int i = 0; i < N; i++)

    {

        dis[i] = INF;

        vis[i] = false;

        pre[i] = -1;

    }

    dis[s] = 0;

    vis[s] = true;

    q.push(s);

    while(!q.empty())

    {

        int u = q.front();

        q.pop();

        vis[u] = false;

        for(int i = head[u]; i != -1; i = edge[i]. next)

        {

            int v = edge[i]. to;

            if(edge[i]. cap > edge[i]. flow &&

                    dis[v] > dis[u] + edge[i]. cost )

            {

                dis[v] = dis[u] + edge[i]. cost;

                pre[v] = i;

                if(!vis[v])

                {

                    vis[v] = true;

                    q.push(v);

                }

            }

        }

    }

    if(pre[t] == -1) return false;

    else return true;

}

//返回的是最大流， cost存的是最小费用

int minCostMaxflow(int s, int t, int &cost)

{

    int flow = 0;

    cost = 0;

    while(spfa(s,t))

    {

        int Min = INF;

        for(int i = pre[t]; i != -1; i = pre[edge[i^1]. to])

        {

            if(Min > edge[i]. cap - edge[i]. flow)

                Min = edge[i]. cap - edge[i]. flow;

        }

        for(int i = pre[t]; i != -1; i = pre[edge[i^1]. to])

        {

            edge[i]. flow += Min;

            edge[i^1]. flow -= Min;

            cost += edge[i]. cost * Min;

        }

        flow += Min;

    }

    return flow;

}

int p[1005];

int l[10005],r[10005],w[10005];

int main()

{

    init();

    int n,m;

    scanf("%d%d",&n,&m);

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

        scanf("%d",&p[i]);

    int S = 0,T = n+3;

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

    {

        int tmp = p[i]-p[i-1];

        if(tmp>=0)addedge(S,i,tmp,0);

        else addedge(i,T,-tmp,0);

        addedge(i+1,i,inf,0);

    }

    for(int i=1;i<=m;i++)

    {

        int a,b,c;scanf("%d%d%d",&a,&b,&c);

        addedge(a,b+1,inf,c);

    }

    int ans1=0,ans2=0;

    ans1 = minCostMaxflow(S,T,ans2);

    printf("%d\n",ans2);

}

相关文章