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

Sample Output

1.50

HINT

数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)

将M个工作人员拆成N个点
拆后的M员工的第k个裂点连某辆车，表示该车是倒数第k个被修的车
因为是倒数第k，所以费用自然要加上后面排队的车的费用
算是一种逆向思维吧
MD n和m搞反了……找错找了半天qwq

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<queue>
  6 #define MAXN (50000+10)
  7 #define MAXM (5000000+10)
  8 using namespace std;
  9 queue<int>q;
 10 bool visit[MAXN];
 11 int pre[MAXN];
 12 int n,m,k,s,e=4999,Ans,Fee;
 13 int num_edge;
 14 int head[MAXN];
 15 int dis[MAXN];
 16 bool used[MAXN];
 17 int INF;
 18 int t[1000][1000];
 19 struct node
 20 {
 21     int to;
 22     int next;
 23     int Flow;//残留网络
 24     int Cost;
 25 } edge[MAXM*2];
 26 
 27 void add(int u,int v,int l,int c)
 28 {
 29     edge[++num_edge].to=v;
 30     edge[num_edge].next=head[u];
 31     edge[num_edge].Flow=l;
 32     edge[num_edge].Cost=c;
 33     head[u]=num_edge;
 34 }
 35 
 36 bool Spfa(int s,int e)
 37 {
 38     memset(pre,-1,sizeof(pre));
 39     memset(dis,0x7f,sizeof(dis));
 40     q.push(s);
 41     dis[s]=0;
 42     used[s]=true;
 43     while (!q.empty())
 44     {
 45         int x=q.front();
 46         q.pop();
 47         for (int i=head[x]; i!=0; i=edge[i].next)
 48             if (dis[x]+edge[i].Cost<dis[edge[i].to] && edge[i].Flow>0)
 49             {
 50                 dis[edge[i].to]=edge[i].Cost+dis[x];
 51                 pre[edge[i].to]=i;
 52                 if (!used[edge[i].to])
 53                 {
 54                     used[edge[i].to]=true;
 55                     q.push(edge[i].to);
 56                 }
 57             }
 58         used[x]=false;
 59     }
 60     return (dis[e]!=INF);
 61 }
 62 
 63 int MCMF(int s,int e)
 64 {
 65     Ans=0,Fee=0;
 66     while (Spfa(s,e))
 67     {
 68         int d=INF;
 69         for (int i=e; i!=s; i=edge[((pre[i]-1)^1)+1].to)
 70             d=min(d,edge[pre[i]].Flow);
 71         for (int i=e; i!=s; i=edge[((pre[i]-1)^1)+1].to)
 72         {
 73             edge[pre[i]].Flow-=d;
 74             edge[((pre[i]-1)^1)+1].Flow+=d;
 75         }
 76         Ans+=d;
 77         Fee+=d*dis[e];
 78     }
 79     return Fee;
 80 }
 81 
 82 int main()
 83 {
 84     memset(&INF,0x7f,sizeof(INF));
 85     scanf("%d%d",&m,&n);
 86     for (int i=1;i<=n;++i)
 87         for (int j=1;j<=m;++j)
 88             scanf("%d",&t[i][j]);
 89     for (int i=1;i<=m*n;++i)
 90     {
 91         add(s,i,1,0);
 92         add(i,s,0,0);
 93     }
 94     for (int i=1;i<=n;++i)
 95     {
 96         add(m*n+i,e,1,0);
 97         add(e,m*n+i,0,0);
 98     }
 99     for (int i=1;i<=n;++i)
100         for (int j=1;j<=m;++j)
101             for (int k=1;k<=n;++k)
102             {
103                 add((j-1)*n+i,m*n+k,1,i*t[k][j]);
104                 add(m*n+k,(j-1)*n+i,0,-i*t[k][j]);
105             }
106     double ans=MCMF(s,e);
107     printf("%.2lf
",ans/n);
108 }