題目鏈接：點擊查看

題目大意：現在有n天需要志愿者，每一天需要招募的人數是Ai個人，現在有m類志愿者，每類志愿者可以在[l,r]天內被招募，需要花費的代價為Ci，現在需要安排一種招募方式，可以使得總花費最少

題目分析：看了題解后看大佬們分析的線性規劃以及動態規劃的解法都是一臉懵逼的，因為是隨著網絡流的標簽進入到這個題目，所以自然要往網絡流的方向去靠攏，看到這個題可以將模型抽象出來，發現是關于區間覆蓋的問題，之前網絡流24題里有一個最長k可重區間集問題，好像可以用那個模型套一下試試，因為招募志愿者，只需要支付一次費用就可以享受[l,r]內所有天的服務，所以我們理所應當建一條邊從l到r+1，流量為無窮大，花費為對應的代價，那么多余的志愿者該怎么辦呢，可以模仿可重區間集的那個問題的思想，開一條特殊的“通道”，將多余的志愿者流過去而不影響最終花費，當然我們需要將源點連向第一個點，同時最后一個點連向匯點，在處理多余志愿者時，我們因為只需要Ai個志愿者，所以-Ai個志愿者是多余的，換句話說，如果我們一共有10個人，現在需要a個志愿者，那么10-a個志愿者是多余的，同理，只不過這里的10個人我們視為0就會出現-Ai這樣的取值了，不過在建邊時正向邊的流量必須非負，這樣我們自然可以加上一個很大的數，用來限流即可，具體建邊方法如下：

源點->第一個點，流量為inf，花費為0

每個點->下一個點，流量為inf-Ai，花費為0

志愿者開始日期->志愿者結束日期+1，流量為inf，花費為Ci

最后一個點->匯點，流量為inf，花費為0

最后解釋一下為什么讓多余的志愿者流過去可以這樣操作，因為我們源點和匯點的流量都設置為了無窮大，所以整張圖最后跑出來的最大流一定是無窮大的，既然每個點到下一個點的這一條道路我們將其用作給多余的志愿者使用的道路，而對于每條這樣的邊，其權值都會比inf少Ai，但既然要保證最后的最大流為inf，少掉的這Ai的流量當然要從帶權值的邊上跑才行，也就達到了限流的目的

說在最后，其實這個題目正常人第一反應都是源點到志愿者建邊，志愿者再到可影響的天數建邊，但是會發現這是一個典型的網絡流無法解決的“一對多”的模式，也就是志愿者的一個單位的流量會影響多個天數，所以我們必須轉換思維模式，才能進行求解

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e3+100;//點const int M=1e5+100;//邊struct Edge {int to,w,cost,next; }edge[M];int head[N],cnt;void addedge(int u,int v,int w,int cost) {edge[cnt].to=v;edge[cnt].w=w;edge[cnt].cost=cost;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].to=u;edge[cnt].w=0;edge[cnt].cost=-cost;edge[cnt].next=head[v];head[v]=cnt++; }int d[N],incf[N],pre[N];bool vis[N];bool spfa(int s,int t) {memset(d,inf,sizeof(d));memset(vis,false,sizeof(vis));memset(pre,-1,sizeof(pre));queue<int>q;q.push(s);vis[s]=true;incf[s]=inf;d[s]=0;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;int w=edge[i].w;int cost=edge[i].cost;if(!w)continue;if(d[v]>d[u]+cost){d[v]=d[u]+cost;pre[v]=i;incf[v]=min(incf[u],w);if(!vis[v]){vis[v]=true;q.push(v);}}}}return pre[t]!=-1; }int update(int s,int t) {int x=t;while(x!=s){int i=pre[x];edge[i].w-=incf[t];edge[i^1].w+=incf[t];x=edge[i^1].to;}return d[t]*incf[t]; }void init() {memset(head,-1,sizeof(head));cnt=0; }int solve(int st,int ed) {int ans=0;while(spfa(st,ed))ans+=update(st,ed);return ans; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);init();int n,m,st=N-1,ed=st-1;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int num;scanf("%d",&num);addedge(i,i+1,inf-num,0);}while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);addedge(u,v+1,inf,w);}addedge(st,1,inf,0);addedge(n+1,ed,inf,0);printf("%d\n",solve(st,ed));return 0; }

?

總結

以上是生活随笔為你收集整理的洛谷 - P3980 [NOI2008]志愿者招募(最小费用最大流+思维建边)的全部內容，希望文章能夠幫你解決所遇到的問題。

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