1070: [SCOI2007]修车

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 5860  Solved: 2487
[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

Sample Output

1.50
 
把修车师傅拆成 n*m个修车师傅 然后具体 //  还是看这里吧http://hzwer.com/2877.html
 
 #include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
const int M=5e5+;
const int INF=0x3f3f3f3f;
int mp[][];
struct node{
   int u,v,flow,cost,next;
}e[M];
int tot,head[N],pre[N],C[N],F[N],V[N],n,m;
void add(int u,int v,int flow,int cost){
   e[tot].u=u;e[tot].v=v;e[tot].flow=flow;e[tot].cost=cost;e[tot].next=head[u];head[u]=tot++;
   e[tot].u=v;e[tot].v=u;e[tot].flow=;e[tot].cost=-cost;e[tot].next=head[v];head[v]=tot++;
}
int SPFA(int s,int t){
    memset(pre,-,sizeof(pre));
    for(int i=;i<=t+;++i) F[i]=,C[i]=INF,V[i]=;
    queue<int>Q;
    Q.push(s);
    C[]=,F[]=INF,V[]=;
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        V[u]=;
        for(int i=head[u];i+;i=e[i].next){
            int v=e[i].v,f=e[i].flow,c=e[i].cost;
            if(f>&&C[v]>C[u]+c) {
                C[v]=C[u]+c;
                pre[v]=i;
                F[v]=min(f,F[u]);
                if(!V[v]) V[v]=,Q.push(v);
            }
        }
    }
    return F[t];
}
int MCMF(int s,int t){
    int ans=,temp;
    while(temp=SPFA(s,t)){
        for(int i=pre[t];i+;i=pre[e[i].u]) {
            ans+=temp*e[i].cost;
            e[i].flow-=temp;
            e[i^].flow+=temp;
        }
    }
    return ans;
}
int main(){
   memset(head,-,sizeof(head));
   scanf("%d%d",&m,&n);
   for(int i=;i<=n;++i)
    for(int j=;j<=m;++j)
    scanf("%d",&mp[i][j]);//mp[i][j],顾客--修车人员
   int st=,ed=m*n+n+;
   for(int i=;i<=n*m;++i) add(,i,,);
    for(int i=n*m+;i<=n*m+n;++i) add(i,ed,,);
    for(int i=;i<=m;++i)
        for(int j=;j<=n;++j)
        for(int k=;k<=n;++k)
       add((i-)*n+j,n*m+k,,mp[k][i]*j);
    int ct=MCMF(st,ed);
    printf("%.2f\n",double(ct)/n);
}
 

最新文章

  1. 穿越之旅之--android中如何执行java命令
  2. Android 获取当前时间问题1
  3. Exception loading sessions from persistent storage
  4. KVC 与 KVO 理解
  5. easyui dialog 扩展load
  6. 尝试用Uplodify
  7. Android图像处理2
  8. C# 读XML文件
  9. SAP Crystal Dashboard Design 2011 win7 x64 安装
  10. 011_hasCycle
  11. SignaLR通信技术
  12. 使用 vue-cli-service inspect 来查看一个 Vue CLI 3 项目的 webpack 配置信息(包括:development、production)
  13. split函数
  14. 重学C语言---03数据和C
  15. xshell各个版本下载
  16. Python交互数据库(Mysql | Mongodb | Redis)
  17. Counting
  18. ZOJ 3962 Seven Segment Display(数位DP)
  19. sublime text 3 配置优化
  20. 团队作业4——第一次项目冲刺(Alpha版本)第一次

热门文章

  1. cmd命令行中无pip命令的解决办法
  2. Android Resourse
  3. ReentrantReadWriteLock及共享锁的实现
  4. IT成长中的龟兔赛跑
  5. 4.shell基本操作简介
  6. 禅道部署(基于 Linux)
  7. muduo网络库源码学习————线程特定数据
  8. Codeforces Round #637 (Div. 2) 题解
  9. string操作大全
  10. Java——异常那些事