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
1 N 1000,1 M 10000, 题目中其他所涉及的数据均 不超过 2^31-1
这个填坑的思想还是蛮妙的
S-1 INF 0
i-i+1 INF - 第 i 天需要人数 0
xi-yi INF 这个人需要的费用
那么这个题是什么意思呢? 首先 INF-a[i] 那里相当于在每条边上挖了个坑
然后我们需要用 xi-yi 这些有费用的边把流量重新填回 INF
连好边然后最小费用最大流即可
- #include<iostream>
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<queue>
- #define MAXN (50000+10)
- #define MAXM (1000000+10)
- using namespace std;
- bool visit[MAXN];
- int pre[MAXN];
- int n,m,s,e,Ans;
- int num_edge;
- int head[MAXN];
- int q[MAXN*100];
- int dis[MAXN];
- bool used[MAXN];
- int INF;
- struct node
- {
- int to;
- int next;
- int Flow;
- int Cost;
- }edge[MAXM*2];
- void add(int u,int v,int l,int c)
- {
- edge[++num_edge].to=v;
- edge[num_edge].next=head[u];
- edge[num_edge].Flow=l;
- edge[num_edge].Cost=c;
- head[u]=num_edge;
- }
- bool Spfa(int s,int e)
- {
- int Head=0,Tail=1;
- memset(pre,-1,sizeof(pre));
- memset(dis,0x7f,sizeof(dis));
- q[1]=s;
- dis[s]=0;
- used[s]=true;
- while (Head<Tail)
- {
- int x=q[++Head];
- for (int i=head[x];i!=0;i=edge[i].next)
- if (dis[x]+edge[i].Cost<dis[edge[i].to] && edge[i].Flow>0)
- {
- dis[edge[i].to]=edge[i].Cost+dis[x];
- pre[edge[i].to]=i;
- if (!used[edge[i].to])
- {
- used[edge[i].to]=true;
- q[++Tail]=edge[i].to;
- }
- }
- used[x]=false;
- }
- return (dis[e]!=INF);
- }
- int MCMF(int s,int e)
- {
- int Fee=0;
- while (Spfa(s,e))
- {
- int d=INF;
- for (int i=e;i!=s;i=edge[((pre[i]-1)^1)+1].to)
- d=min(d,edge[pre[i]].Flow);
- for (int i=e;i!=s;i=edge[((pre[i]-1)^1)+1].to)
- {
- edge[pre[i]].Flow-=d;
- edge[((pre[i]-1)^1)+1].Flow+=d;
- }
- Fee+=d*dis[e];
- }
- return Fee;
- }
- int main()
- {
- int x,y,c;
- memset(&INF,0x7f,sizeof(INF));
- scanf("%d%d",&n,&m);
- s=0,e=n+1;
- add(s,1,INF,0); add(1,s,0,0);
- for (int i=1;i<=n;++i)
- {
- scanf("%d",&x);
- add(i,i+1,INF-x,0); add(i+1,i,0,0);
- }
- for (int i=1;i<=m;++i)
- {
- scanf("%d%d%d",&x,&y,&c);
- add(x,y+1,INF,c); add(y+1,x,0,-c);
- }
- printf("%d",MCMF(s,e));
- }
来源: http://www.bubuko.com/infodetail-2545998.html