首页 > 代码库 > 洛谷 P2053 [SCOI2007]修车
洛谷 P2053 [SCOI2007]修车
题目描述
同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。
说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
输入输出格式
输入格式：
第一行有两个数M,N，表示技术人员数与顾客数。
接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。
输出格式：
最小平均等待时间，答案精确到小数点后2位。
输入输出样例
输入样例#1：
2 23 21 4
输出样例#1：
1.50
说明
(2<=M<=9,1<=N<=60), (1<=T<=1000)
费用流
建好图 跑模板。
屠龙宝刀点击就送
#include <ctype.h>#include <cstring>#include <cstdio>#include <queue>#define M 50005#define inf 0x7fffffffusing namespace std;void read(int &x){ x=0;bool f=0; register char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch==‘-‘) f=1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘; x=f?(~x)+1:x;}struct Edge{ int next,to,flow,value; Edge (int next=0,int to=0,int flow=0,int value=http://www.mamicode.com/0) : next(next),to(to),flow(flow),value(value) {}}edge[M<<1];bool vis[M<<1];int ti[80][80],m,n,head[M<<1],cnt=1,fa[M<<1],dis[M<<1];void insert(int u,int v,int w,int l){ edge[++cnt]=Edge(head[u],v,w,l); head[u]=cnt;}bool spfa(int s,int t){ for(int i=0;i<=t;i++) {dis[i]=inf;vis[i]=0;} vis[s]=1; dis[s]=0; fa[s]=0; queue<int>q; q.push(s); while(!q.empty()) { int x=q.front(); q.pop(); vis[x]=0; for(int i=head[x];i;i=edge[i].next) { int v=edge[i].to; if(dis[v]>dis[x]+edge[i].value&&edge[i].flow>0) { dis[v]=dis[x]+edge[i].value; fa[v]=i; if(!vis[v]) { vis[v]=1; q.push(v); } } } } return dis[t]<inf;}int dinic(int s,int t){ int cost=0; for(;spfa(s,t);) { int x=dis[t]; for(int i=t;i!=s;i=edge[fa[i]^1].to) { edge[fa[i]].flow-=x; edge[fa[i]^1].flow+=x; } cost+=dis[t]; } return cost;}int main(){ read(m); read(n); int s=0,t=n*m+n+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(ti[i][j]); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) { insert((i-1)*n+j,n*m+k,1,ti[k][i]*j); insert(n*m+k,(i-1)*n+j,0,-ti[k][i]*j); } for(int i=1;i<=m*n;i++) { insert(s,i,1,0); insert(i,s,0,0); } for(int i=n*m+1;i<t;i++) { insert(i,t,1,0); insert(t,i,0,0); } printf("%.2lf",dinic(s,t)*1.0/n); return 0;}
洛谷 P2053 [SCOI2007]修车
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。