杭电第二场1005 New Equipments 二次函数离散化+费用流
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6767
题目大意：有n个工人，m个设备。每个工人有3个属性：a[i], b[i], c[i]; 如果第i个人分配第j个设备的代价是 。
输出给i个工人分配设备的最小代价。
思路：典型的费用流，不过m很大，但是根据代价是一个二次函数。我们取对称轴的周围50个点就可以了。然后离散化跑费用流。流量为i时，spfa增广一次就最大流加1.就是给i+1个工人分配设备的最小代价。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL maxn=3000;
struct Mcmf_flow{
bool vis[maxn];
LL dis[maxn];
LL pre[maxn];
LL last[maxn];
LL flow[maxn];
LL zdl, fy;
LL s1[maxn], sum[maxn], tot=0;
//dis最小花费;pre每个点的前驱；last每个点的所连的前一条边；flow源点到此处的流量
struct Edge {
LL to,next,flow,dis;//flow流量 dis花费
} e[1000000+10];
LL head[maxn],cut;
queue <LL> q;
int N=0;
void init(int n){
N=n;
memset(s1, 0, sizeof(LL)*(n+60));
memset(sum, 0, sizeof(LL)*(n+60));
memset(head,-1,sizeof(LL)*(n+60));
tot=0;
cut=-1;//初始化
zdl=fy=0;
}
void add_e(LL from,LL to,LL flow,LL dis) {
e[++cut].next=head[from];
e[cut].to=to;
e[cut].flow=flow;
e[cut].dis=dis;
head[from]=cut;
}
void add(LL x, LL y, LL z, LL f){
add_e(x,y,z,f);
add_e(y,x,0,-f);
}
bool spfa(LL s,LL t) {
memset(dis,0x7f,sizeof(LL)*(N+60));
memset(flow,0x7f,sizeof(LL)*(N+60));
memset(vis,0,sizeof(bool)*(N+60));
q.push(s);
vis[s]=1; dis[s]=0; pre[t]=-1;
while (!q.empty()) {
LL now=q.front();
q.pop(); vis[now]=0;
for (LL i=head[now]; i!=-1; i=e[i].next) {
if (e[i].flow>0 && dis[e[i].to]>dis[now]+e[i].dis) { //正边
dis[e[i].to]=dis[now]+e[i].dis;
pre[e[i].to]=now;
last[e[i].to]=i;
flow[e[i].to]=min(flow[now],e[i].flow);//
if (!vis[e[i].to]) {
vis[e[i].to]=1;
q.push(e[i].to);
}
}
}
}
return pre[t]!=-1;
}
void MCMF(LL s, LL t) {
while (spfa(s,t)) {
LL now=t;
zdl+=flow[t];
fy+=flow[t]*dis[t];
sum[++tot]=fy;//得到sum[]
s1[tot]=sum[tot]-sum[tot-1];//得到s1[]
while (now!=s) {
//从源点一直回溯到汇点
e[last[now]].flow-=flow[t];//flow和dis容易搞混
e[last[now]^1].flow+=flow[t];
now=pre[now];
}
}
}
}min_Flow;
LL a[55], b[55], c[55];
vector<LL> G[55], fy[55];
LL Ls[3000], tot=0;
void getE(int pos, LL m){
LL x=-b[pos]/(2*a[pos]);
LL R=max(x, 1LL);
int sumL=0;
for(LL i=R; i<=R+25&&i<=m; i++, sumL++){
G[pos].push_back(i);
fy[pos].push_back(a[pos]*i*i+b[pos]*i+c[pos]);
Ls[++tot]=i;
}
LL L=min(x-1, m);
int sumR=50-sumL;
for(LL i=L; i>=1&&sumR>0; sumR--, i--){
G[pos].push_back(i);
fy[pos].push_back(a[pos]*i*i+b[pos]*i+c[pos]);
Ls[++tot]=i;
}
for(LL i=R+sumL; i<=R+sumL+sumR&&i<=m; i++){
G[pos].push_back(i);
fy[pos].push_back(a[pos]*i*i+b[pos]*i+c[pos]);
Ls[++tot]=i;
}
}
int main() {
int t, n, m;
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &m);
tot=0;
for(int i=1; i<=n; i++){
G[i].clear(); fy[i].clear();
}
for(int i=1; i<=n; i++){
scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
getE(i, m);
}
sort(Ls+1, Ls+1+tot);
int cnt=unique(Ls+1, Ls+1+tot)-Ls-1;
min_Flow.init(cnt);
for(int i=1; i<=n; i++){
for(int k=0; k<G[i].size(); k++){
int x=lower_bound(Ls+1, Ls+cnt+1, G[i][k])-Ls+50;
min_Flow.add(i, x, 1, fy[i][k]);
}
}
int S=0, T=cnt+51;
for(int i=1; i<=n; i++){
min_Flow.add(S, i, 1, 0);
}
for(int i=1; i<=cnt; i++){
min_Flow.add(i+50, T, 1, 0);
}
min_Flow.MCMF(S, T);
for(int i=1; i<=n; i++){
printf("%lld%c", min_Flow.sum[i], (i==n)?'\n':' ');
}
}
return 0;
}
京东开奖150人在聊