題目鏈接：http://www.lydsy.com/JudgeOnline/problem.php?id=1061

1061: [Noi2008]志愿者招募

Time Limit: 20 Sec??Memory Limit: 162 MB
Submit: 3878??Solved: 2367
[Submit][Status][Discuss]

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。

?

神題啊。根本不會寫。

還是膜拜這篇題解：https://www.byvoid.com/blog/noi-2008-employee/

?

#include<cstdio> #include<cstring> #include<algorithm> #define maxn 1005 #define maxm 10005 using namespace std; const int inf=0x7fffffff; int ans,n,m,tot,s,t,h[maxn],way[maxm*4],next[maxm*4],ww[maxm*4],cap[maxm*4],a[maxn],pre[maxn]; int read(){int x=0,f=1;char ch;for(ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';return x*f; } void add(int x,int y,int w,int c){way[++tot]=y;next[tot]=h[x];h[x]=tot;ww[tot]=w;cap[tot]=c;} void insert(int x,int y,int w,int c=inf){add(x,y,w,c);add(y,x,-w,0);} int head,tail,d[maxn+10],dist[maxn]; bool v[maxn]; bool spfa(){memset(v,0,sizeof(v));v[s]=1;pre[s]=-1;for(int i=0;i<=t;i++)dist[i]=inf;dist[s]=0;head=0;tail=1;d[0]=s;while(head!=tail){int x=d[head];head++;if(head>maxn)head=0;for(int j=h[x];j;j=next[j])if(cap[j]&&dist[way[j]]>dist[x]+ww[j]){dist[way[j]]=dist[x]+ww[j];pre[way[j]]=j;if(!v[way[j]]){v[way[j]]=1;d[tail++]=way[j];if(tail>maxn)tail=0;}}v[x]=0;}return dist[t]!=inf; } int find(){int delt=inf,x=0;for(int j=t;j!=s;j=way[pre[j]^1]){delt=min(delt,cap[pre[j]]);}for(int j=t;j!=s;j=way[pre[j]^1]){x=x+delt*ww[pre[j]];cap[pre[j]]-=delt;cap[pre[j]^1]+=delt;}return x; } int main(){n=read();m=read();tot=1;for(int i=1;i<=n;i++)a[i]=read();for(int i=1,x,y,z;i<=m;i++){x=read();y=read();z=read();insert(x,y+1,z);}s=0;t=n+2;for(int i=1;i<=n+1;i++){int x=a[i]-a[i-1];if(x>=0)insert(s,i,0,x);else insert(i,t,0,-x);if(i>1)insert(i,i-1,0);}while(spfa())ans+=find();printf("%d\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/longshengblog/p/6056269.html

總結

以上是生活随笔為你收集整理的BZOJ1061: [Noi2008]志愿者招募的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。