[SCOI2007] 修车
题目描述
同一时刻有 \(N\) 位车主带着他们的爱车来到了汽车维修中心。
维修中心共有 \(M\) 位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。
现在需要安排这 \(M\) 位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。
说明:顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
输入格式
第一行有两个数 \(M,N\),表示技术人员数与顾客数。
接下来 \(N\) 行,每行 \(M\) 个整数。第 \(i+1\) 行第 \(j\) 个数表示第 \(j\) 位技术人员维修第 \(i\) 辆车需要用的时间 \(T_{i,j}\)。
输出格式
最小平均等待时间,答案精确到小数点后 \(2\) 位。
样例 #1
样例输入 #1
2 2
3 2
1 4
样例输出 #1
1.50
提示
对于 \(100\%\) 的数据,\(2\le M\le 9\),\(1\le N\le 60\),\(1\le T\le 10^3\)。
倒数第 \(i\) 个修的车,他的时间在总等待时间内会被计算 \(i\) 次。
把一个工人拆成 \(n\) 份,表示他倒数第 \(i\) 个修的车。然后给第 \(i\) 个车分配他是 \(k\) 人倒数第 \(j\) 个修的车,流量 1 费用 \(j\times t_{i,k}\)
#include<bits/stdc++.h>
using namespace std;
const int N=2005,M=300005;
struct edge{
int u,v,nxt,f,w;
}e[M];
struct node{
int v,w;
bool operator<(const node&n)const{
return w>n.w;
}
};
priority_queue<node>q;
int m,n,p[N],d[N],h[N],hd[N],T,e_num=1,l,r,v[N],t[65][10],ans;
void add_edge(int u,int v,int f,int w)
{
e[++e_num]=(edge){u,v,hd[u],f,w};
hd[u]=e_num;
e[++e_num]=(edge){v,u,hd[v],0,-w};
hd[v]=e_num;
}
void spfa()
{
static int q[N*N];
memset(h,0x7f,sizeof(h));
h[q[l=r=1]=0]=0;
while(l<=r)
{
for(int i=hd[q[l]];i;i=e[i].nxt)
{
if(e[i].f&&h[e[i].v]>h[q[l]]+e[i].w)
{
h[e[i].v]=h[q[l]]+e[i].w;
if(!v[e[i].v])
v[q[++r]=e[i].v]=1;
}
}
v[q[l++]]=0;
}
}
int dijkstra()
{
memset(d,0x7f,sizeof(d));
memset(v,0,sizeof(v));
d[0]=0;
q.push((node){0,0});
while(!q.empty())
{
int k=q.top().v;
q.pop();
if(v[k])
continue;
v[k]=1;
for(int i=hd[k];i;i=e[i].nxt)
{
if(e[i].f&&d[e[i].v]>d[k]+e[i].w+h[k]-h[e[i].v])
{
d[e[i].v]=d[k]+e[i].w+h[k]-h[e[i].v];
p[e[i].v]=i;
q.push((node){e[i].v,d[e[i].v]});
}
}
}
return v[T];
}
signed main()
{
scanf("%d%d",&m,&n);
T=n+n*m+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",t[i]+j);
for(int i=1;i<=n;i++)
{
add_edge(0,i,1,0);
for(int j=1;j<=m;j++)
for(int k=1;k<=n;k++)
add_edge(i,n+(j-1)*n+k,1,k*t[i][j]);
}
for(int i=1;i<=n*m;i++)
add_edge(n+i,T,1,0);
spfa();
int s=0;
while(dijkstra())
{
for(int i=0;i<=T;i++)
h[i]+=d[i];
int mnf=1000000000;
for(int i=T;i;i=e[p[i]].u)
mnf=min(mnf,e[p[i]].f);
for(int i=T;i;i=e[p[i]].u)
e[p[i]].f-=mnf,e[p[i]^1].f+=mnf;
s+=mnf;
ans+=mnf*h[T];
}
printf("%.2lf",1.0*ans/n);
}
标签:le,int,修车,edge,++,num,SCOI2007,hd
From: https://www.cnblogs.com/mekoszc/p/17895587.html