題目鏈接：點擊查看
題目大意：給出 n 個仆人可以召喚，場上最多可以同時存在 k 個仆人，每個仆人帶有一個屬性 a 和屬性 b ，仆人本身的價值為 a[ i ] ，當召喚出仆人 i 后，場上的所有仆人價值都加 b[ i ] ，每個仆人只能被召喚（銷毀）一次，問如何確定召喚順序，可以使最后場上的仆人價值總和最大，給出一種召喚方案
題目分析：因為所有的 a[ i ] 都是非負的，所以顯然最后場上的仆人個數為 k 個是最優的
其次，如果場上只能有 k 個仆人的話，那么其余 n - k 個仆人的屬性 a 就失去了意義，不過可以讓他們當炮灰，也就是在召喚出來充分利用其價值 b 后，再將其銷毀，不難看出，當其被召喚出來之后，其價值就已經發揮到最大了，所以下一回合直接將其銷毀是最優的選擇
綜上所述，最優的方案可以簡述為兩個點，第一點是所有的仆人都需要召喚，只不過有些仆人當炮灰了而已，第二點是 n 個仆人的召喚順序決定了最后的權值和
那么我們只需要給 n 個仆人分配一個合理的順序然后再依次召喚就好了，這里還有一個思維點需要想到，那就是 n 個仆人可以大體分為三段：
1 ~ k - 1：這 k - 1 個仆人最后是保留在場上的 k ~ n - 1 ：這 n - k 個仆人是炮灰 1 ： 最后的這個仆人是當炮灰都送完人頭之后，最后再上場，并且保留在場上
大體分成三段后，不難看出讓第一段的仆人先登場，然后恰好留出了一個位置，讓第二段的炮灰去送人頭，給第一段的仆人增加權值，然后再讓最后的仆人登場是一種最優的方法
既然這樣，就不難看出每個位置的權值大小了：
i ∈ [ 1 ,?k - 1 ]：a[ i ] + b[ i ] * ( i - 1 ) i ∈ [ k , n?- 1 ]：b[ i ] * ( k - 1 ) i? == n ：a[ i ] + b[ i ] * ( k - 1 )
然后因為數據比較小，可以用最大費用最大流來求解，一方面可以限制流量，另一方面可以求動態的最優方案，建圖方法如下：
超級源點 -> 每個仆人，流量為 1 ，花費為 0 每個仆人 -> 每個位置，流量為 1 ，花費為上述分情況討論的結果 每個位置 -> 超級匯點，流量為 1 ，花費為 0
建好圖后直接跑模板就好了，關于路徑輸出這里就不多贅述了，比較簡單
代碼：
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=210;//點const int M=N*N;//邊int a[N],b[N],pos[N];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,0xcf,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()
{
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int w;cin>>w;while(w--){init();int n,k,st=N-1,ed=st-1;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d%d",a+i,b+i);for(int i=1;i<=n;i++){addedge(st,i,1,0);addedge(i+n,ed,1,0);}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(j<=k-1)addedge(i,j+n,1,a[i]+b[i]*(j-1));else if(j==n)addedge(i,j+n,1,a[i]+b[i]*(k-1));elseaddedge(i,j+n,1,b[i]*(k-1));}solve(st,ed);for(int i=1;i<=n;i++)for(int j=head[i];j!=-1;j=edge[j].next)if(edge[j].to>n&&edge[j].to<=2*n&&edge[j].w==0)pos[edge[j].to-n]=i;printf("%d\n",k+(n-k)*2);for(int i=1;i<=n;i++){printf("%d ",pos[i]);if(i>k-1&&i!=n)printf("%d ",-pos[i]);}puts("");}return 0;
}
?
總結
以上是生活随笔 為你收集整理的CodeForces - 1354F Summoning Minions(最大费用最大流) 的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網站內容還不錯，歡迎將生活随笔 推薦給好友。
