題目鏈接：點擊查看

題目大意：給出 n 個工人，再給出 m 臺機器，第 i 個工人和第 j 臺機器匹配的代價是 a[ i ] * j * j + b[ i ] * j + c[ i ] ，問如何進行匹配，可以使得代價和最小

題目分析：代價可以視為二次函數，且數據范圍限制了系數 a 是大于 0 的，換句話說，二次函數的開口向上，這樣函數就存在著最小值

考慮 n 最大只有 50 ，所以我們可以對于每個工人的二次函數，求出與其匹配所花費代價的前 n 小的位置，求出這些位置之后，直接將工人與機器連邊求解就好了，因為每個工人都與 n 個機器建邊，所以最終一定可以達到完全匹配，最終有 n 個工人，n * n 臺機器，而 spfa 實現的費用流總時間復雜度會退化為 n^5 ，但常數較小，跑起來還是非常快的

代碼：

#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> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=3e3+100;//點const int M=5e5+100;//邊LL res[60],a[60],b[60],c[60];vector<int>node[60];//每個i的前n小的位置 vector<int>ve;//離散化 struct Edge {int to,w,next;LL cost; }edge[M];int head[N],cnt;void addedge(int u,int v,int w,LL 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++; }LL d[N];int incf[N],pre[N];bool vis[N];bool spfa(int s,int t) {memset(d,0x3f,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;LL 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; }LL 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() {ve.clear();for(int i=0;i<60;i++)node[i].clear(); memset(head,-1,sizeof(head));cnt=0; }void solve(int st,int ed) {LL ans=0;int tot=0;while(spfa(st,ed)){ans+=update(st,ed);res[++tot]=ans;} }LL fun(int i,int x) {return a[i]*x*x+b[i]*x+c[i]; }void discreate() {sort(ve.begin(),ve.end());ve.erase(unique(ve.begin(),ve.end()),ve.end()); }int get_num(int x) {return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+1; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){init();int n,m,st=N-1,ed=st-1;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%lld%lld%lld",a+i,b+i,c+i);int pos=-(b[i]/(a[i]*2));//對稱軸pos=min(pos,m);pos=max(pos,1);for(int j=pos,cnt=0;j>=1&&cnt<=n;j--,cnt++)//往前找n個 node[i].push_back(j);for(int j=pos+1,cnt=0;j<=m&&cnt<=n;j++,cnt++)//往后找n個 node[i].push_back(j);sort(node[i].begin(),node[i].end(),[&](int x,int y)//排序 {return fun(i,x)<fun(i,y);});node[i].resize(n);//只保留前n大 for(auto it:node[i])ve.push_back(it);}discreate();for(int i=1;i<=ve.size();i++)addedge(i+n,ed,1,0);for(int i=1;i<=n;i++){addedge(st,i,1,0);for(auto it:node[i]){int pos=get_num(it);addedge(i,pos+n,1,fun(i,it));}}solve(st,ed);for(int i=1;i<=n;i++)printf("%lld%c",res[i],i==n?'\n':' ');}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU多校2 - 6767 New Equipments(最小费用最大流)的全部內容，希望文章能夠幫你解決所遇到的問題。

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