1070: [SCOI2007]修车
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 3721 Solved: 1507
[Submit][Status][Discuss]
Description
同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
Input
第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。
Output
最小平均等待时间，答案精确到小数点后2位。
Sample Input
2 2
3 2
1 4
3 2
1 4
Sample Output
1.50
HINT
数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)
#include<cstdio>
#define INF 1000000000
using namespace std;
int n,m,tot,edgenum,ans;
int id[100][100],Id[100],a[100][100];
int vet[500010],next[500010],head[500010],maxv[500010],cost[500010],dis[500010],flag[500010],q[500010],last[500010],pre[500010];
void add(int u,int v,int w,int z)
{
vet[++edgenum]=v;
next[edgenum]=head[u];
head[u]=edgenum;
maxv[edgenum]=w;
cost[edgenum]=z;
}
int spfa()
{
for (int i=0;i<=tot;i++){dis[i]=INF;flag[i]=0;}
int p1=-1,p2=0;
q[0]=0;dis[0]=0;flag[0]=1;
while (p1<p2)
{
int u=q[++p1];
flag[u]=0;
for (int e=head[u];e;e=next[e])
{
if (maxv[e]<=0) continue;
int v=vet[e];
if (dis[u]+cost[e]<dis[v])
{
dis[v]=dis[u]+cost[e];
last[v]=e;pre[v]=u;
if (!flag[v]){flag[v]=1;q[++p2]=v;}
}
}
}
if (dis[tot]==INF) return 0;else return 1;
}
void work()
{
ans+=dis[tot];
int u=tot;
while (u)
{
int e=last[u];
maxv[e]--;
if (e%2) maxv[e+1]++;else maxv[e-1]++;
u=pre[u];
}
}
int main()
{
scanf("%d%d",&m,&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
scanf("%d",&a[j][i]);
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
id[i][j]=++tot;
for (int i=1;i<=n;i++)
Id[i]=++tot;
tot++;
for (int i=1;i<=n;i++){add(0,Id[i],1,0);add(Id[i],0,0,0);}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
for (int k=1;k<=n;k++){add(Id[i],id[j][k],1,a[j][i]*k);add(id[j][k],Id[i],0,-a[j][i]*k);}
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++){add(id[i][j],tot,1,0);add(tot,id[i][j],0,0);}
while (spfa()) work();
printf("%.2lf\n",(double)ans/n);
}
评论 (0)
