首页 > 其他分享 >[SCOI2007] 修车

[SCOI2007] 修车

时间:2023-12-11 21:22:59浏览次数:31  
标签:le int 修车 edge ++ num SCOI2007 hd

[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

相关文章

  • P4163 [SCOI2007]排列
    Problem给一个数字串\(s\)和正整数\(d\),统计\(s\)有多少种不同的排列能被\(d\)整除(可以有前导\(0\))。多组数据。\(\left\verts\right\vert\le10,1\led\le1000,1\let\le15\)Input第一行一个整数\(t\),表示数据组数。接下来\(t\)行,每行一个数字串\(s\)......
  • NC20259 [SCOI2007]降雨量
    题目链接题目题目描述我们常常会说这样的话:“X年是自Y年以来降雨量最多的”。它的含义是X年的降雨量不超过Y年,且对于任意Y<Z<X,Z年的降雨量严格小于X年。例如2002,2003,2004和2005年的降雨量分别为4920,5901,2832和3890,则可以说“2005年是自2003年以来最多的”,但不能说“2005年是自......
  • P2470 [SCOI2007]压缩
    传送门区间DP好题,看到这题很容易想到设\(f[i][j]\)为区间\(i\)~\(j\)内的最短折叠,那么转移方程就为:\[f[i][j]=min_{k=i}^{j-1}(f[i][j],f[i][k]+f[k+1][j])\]然鹅这......
  • 【SCOI2007】k短路(A_)
    考虑用\(A^*\)维护这个东西,由于其它题解都讲得很清楚\(A^*\)的原理了,我就在这里说一下这题需要注意的地方。按照\(A^*\)的套路,我们要把估价函数设为当前点到\(b\)......