2020hdu多校round2第五题New Equipments

本文主要是介绍2020hdu多校round2第五题New Equipments，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=6767

题解

一个工人对应一个二次函数，尽量往函数对称轴配对。而又n个工人，所以每个工人一定能连到对称轴周围n个最近的点之一。所以从n个工人节点向他的对称轴周围n个点连边，边流量1，费用 $a_ij^2+b_ij+c_i$ ，完了超级源流量限制为k，枚举k建立n次图，跑n次费用流。

AC代码

尽量不用宏定义字符串替换，括号老是丢。找错找一天。。哭了。

#include<bits/stdc++.h>
#define Pair pair<long long, long long>
#define fi first
#define se second
//#define AddEdge(x,y,f,z) add_edge(x,y,f,z);add_edge(y,x,0,-z);
// #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)
// char buf[1<<20],*p1=buf,*p2=buf;
using namespace std;
const int NN=5010;
long long INF=1000000000000000000ll;
const int MM=50010;
inline int read()
{char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
int N,M,S,T;
struct node
{int u,v;long long f,w;
}edge[MM];
int num=0;
vector<int>con[NN];
inline void add_edge(int x,int y,long long f,long long z)
{edge[num].u=x;edge[num].v=y;edge[num].f=f;edge[num].w=z;con[x].push_back(num);num++;
}
inline void AddEdge(int x,int y,long long f,long long z) {add_edge(x,y,f,z);add_edge(y,x,0,-z);}
long long h[NN],dis[NN];
int PrePoint[NN],PreEdge[NN];
Pair Dij()
{long long ansflow=0,anscost=0;for(int i=1;i<=N;i++)h[i]=0;while(1){priority_queue<Pair>q;for(int i=1;i<=N;i++)dis[i]=INF;dis[S]=0;q.push(make_pair(0,S));while(q.size()!=0){Pair p=q.top();q.pop();if(-p.fi!=dis[p.se]) continue;if(p.se==T) break;int up=con[p.se].size();for(int ii=0;ii<up;ii++){int i=con[p.se][ii];long long nowcost=edge[i].w+h[p.se]-h[edge[i].v];if(edge[i].f>0&&dis[edge[i].v]>dis[p.se]+nowcost){dis[edge[i].v]=dis[p.se]+nowcost;q.push(make_pair(-dis[edge[i].v],edge[i].v));PrePoint[edge[i].v]=p.se;PreEdge[edge[i].v]=i;}}}if(dis[T]>=INF) break;for(int i=0;i<=N;i++) h[i]+=dis[i];long long nowflow=INF;for(int now=T;now!=S;now=PrePoint[now])nowflow=min(nowflow,edge[PreEdge[now]].f);for(int now=T;now!=S;now=PrePoint[now])edge[PreEdge[now]].f-=nowflow,edge[PreEdge[now]^1].f+=nowflow;ansflow+=nowflow;anscost+=nowflow*h[T];}return make_pair(ansflow,anscost);
}
map<int,int>ma;
long long a[NN],b[NN],c[NN];
vector<int>from[NN];
int rec[NN];
int main(){int t;scanf("%d",&t);while(t--){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%lld%lld%lld",a+i,b+i,c+i);}int cnt=0;int gs=n/2+n%2;for(int i=1;i<=n;i++){if(b[i]>0){for(int j=1;j<=n;j++){if(ma[j]==0)ma[j]=++cnt;from[ma[j]].push_back(i);rec[ma[j]]=j;}}else{int mid=-b[i]/(a[i]<<1);if(mid<gs){for(int j=1;j<=n;j++){if(ma[j]==0)ma[j]=++cnt;from[ma[j]].push_back(i);rec[ma[j]]=j;}}else{if(mid+gs>m){for(int j=m-n+1;j<=m;j++){if(ma[j]==0)ma[j]=++cnt;from[ma[j]].push_back(i);rec[ma[j]]=j;}}else{for(int j=mid-gs+1;j<=mid+gs;j++){if(ma[j]==0)ma[j]=++cnt;from[ma[j]].push_back(i);rec[ma[j]]=j;}}}}}N=n+3+cnt;for(int k=1;k<=n;k++){for(int i=1;i<=N;i++){con[i].clear();}num=0;for(int i=1;i<=cnt;i++){int up=from[i].size();int jj=rec[i];for(int j=0;j<up;j++){int fr=from[i][j];AddEdge(fr+2,i+n+2,1,a[fr]*jj*jj+b[fr]*jj+c[fr]);}}for(int i=1;i<=n;i++){AddEdge(2,i+2,1,0);}for(int i=n+2+1;i<=n+2+cnt;i++){AddEdge(i,N,1,0);}AddEdge(1,2,k,0);// printf("%d\n",num);// for(int i=0;i<num;i++){// 	printf("%d %d %lld %lld\n",edge[i].u,edge[i].v,edge[i].f,edge[i].w);// }S=1;T=N;Pair ans=Dij();if(k==n)printf("%lld",ans.se);else printf("%lld ",ans.se);}printf("\n");for(int i=1;i<=cnt;i++)from[i].clear();ma.clear();}return 0;
}