首页 > 代码库 > 【bzoj】 1070: [SCOI2007]修车
【bzoj】 1070: [SCOI2007]修车
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)
一个拆了很多很多点的网络流模型。（想法其实是先考虑一个修理师的情况，再考虑多个的情况）
把每个修理师拆成n个点，一辆车分别想着n个点连边，容量为1，费用为t * x 其中x = 1, 2, 3 ... n，表示在这之后修理车的人要总共等待t, t * 2, t * 3, t * 4...时间
然后跑一边最小费用最大流就可以了。
1 #include<queue> 2 #include<cstdio> 3 #include<iostream> 4 #define MAXN 100010 5 6 using namespace std; 7 8 const int INF=0x7fffffff; 9 10 int a[1010][1010],fee[MAXN],pre[MAXN]; 11 12 int n,m,src,decc,ans; 13 14 struct node { 15 int to; 16 int cost; 17 int next; 18 int val; 19 }; 20 node e[MAXN*2]; 21 22 int head[MAXN],tot=1; 23 24 bool vis[MAXN]; 25 26 queue<int> q; 27 28 inline void read(int&x) { 29 int f=1;x=0;char c=getchar(); 30 while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();} 31 while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();} 32 x=x*f; 33 } 34 35 inline void add(int x,int y,int val,int cost) { 36 e[++tot].to=y; 37 e[tot].val=val; 38 e[tot].cost=cost; 39 e[tot].next=head[x]; 40 head[x]=tot; 41 } 42 43 inline void add_edge(int x,int y,int val,int cost) { 44 add(x,y,val,cost); 45 add(y,x,0,-cost); 46 } 47 48 inline int min_flow() { 49 int flow=INF; 50 for(int i=pre[decc];i;i=pre[e[i^1].to]) 51 flow=min(flow,e[i].val); 52 for(int i=pre[decc];i;i=pre[e[i^1].to]) 53 e[i].val-=flow,e[i^1].val+=flow; 54 return flow; 55 } 56 57 inline bool spfa() { 58 for(int i=1;i<=decc;i++) fee[i]=INF; 59 fee[src]=0; 60 vis[src]=true; 61 while(!q.empty()) q.pop(); 62 q.push(src); 63 while(!q.empty()) { 64 int u=q.front(); 65 q.pop(); 66 vis[u]=false; 67 for(int i=head[u];i;i=e[i].next) { 68 int to=e[i].to; 69 if(fee[u]+e[i].cost<fee[to]&&e[i].val) { 70 fee[to]=fee[u]+e[i].cost; 71 pre[to]=i; 72 if(!vis[to]) { 73 q.push(to); 74 vis[to]=true; 75 } 76 } 77 } 78 } 79 return fee[decc]!=INF; 80 } 81 82 inline void build_graph() { 83 for(int i=1;i<=n;i++) 84 for(int j=1;j<=m;j++) 85 for(int k=1;k<=n;k++) 86 add_edge(i,j*n+k,1,a[i][j]*k); 87 src=http://www.mamicode.com/n*m+n+1;decc=n*m+n+2; 88 for(int i=1;i<=n;i++) 89 add_edge(src,i,1,0); 90 for(int i=n+1;i<=n*m+n;i++) 91 add_edge(i,decc,1,0); 92 } 93 94 int main() { 95 read(m);read(n); 96 for(int i=1;i<=n;i++) 97 for(int j=1;j<=m;j++) 98 read(a[i][j]); 99 build_graph();100 while(spfa()) ans+=min_flow()*fee[decc];101 printf("%.2lf\n",(double)ans/n);102 return 0;103 }
【bzoj】 1070: [SCOI2007]修车
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。