1070: [SCOI2007]修车

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

HINT

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

最小费用最大流

然而bzoj TLE

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 
 7 const int INF=0x7f7f7f7f;
 8 const int N=1005;
 9 const int M=100001;
10 const int T=1001;
11 
12 struct Edge
13 {
14     int from,to,v,c,next;//from点到to点 v代表容量 c代表花费 next下一条边
15 }E[M];
16 int node=1;
17 int head[N],from[N],dis[N],vis[N];
18 
19 int n,m;
20 double ans;
21 int t[61][10];
22 
23 void ins(int from,int to,int v,int c)
24 {
25     node++;
26     E[node]=(Edge){from,to,v,c,head[from]};
27     head[from]=node;
28 }
29 
30 void insert(int from,int to,int v,int c)
31 {
32     ins(from,to,v,c);ins(to,from,0,-c);
33 }
34 
35 bool spfa()
36 {
37     queue<int> Q;
38     memset(dis,0x7f,sizeof(dis));
39     Q.push(0);dis[0]=0;vis[0]=1;
40     while(!Q.empty())
41     {
42         int q=Q.front();Q.pop();
43         for(int i=head[q];i;i=E[i].next)
44             if(E[i].v>0&&dis[q]+E[i].c<dis[E[i].to])
45             {
46                 dis[E[i].to]=dis[q]+E[i].c;
47                 from[E[i].to]=i;
48                 if(!vis[E[i].to])
49                 {
50                     Q.push(E[i].to);
51                     vis[E[i].to]=1;
52                 }
53             }
54         vis[q]=0;
55     }
56     return dis[T]!=INF;
57 }
58 
59 void mcf()
60 {
61     int x=INF;
62     for(int i=from[T];i;i=from[E[i].from])
63         x=min(E[i].v,x);
64     for(int i=from[T];i;i=from[E[i].from])
65     {
66         ans+=x*E[i].c;
67         E[i].v-=x;E[i^1].v+=x;
68     }
69 }
70 
71 int main()
72 {
73     scanf("%d %d",&m,&n);
74     for(int i=1;i<=n;i++)
75         for(int j=1;j<=m;j++)
76             scanf("%d",&t[i][j]);
77     for(int i=1;i<=n*m;i++)
78         insert(0,i,1,0);
79     for(int i=n*m+1;i<=n*m+n;i++)
80         insert(i,T,1,0);
81     for(int i=1;i<=m;i++)
82         for(int j=1;j<=n;j++)
83             for(int k=1;k<=n;k++)
84                 insert((i-1)*n+j,n*m+k,1,t[k][i]*j);
85     while(spfa()) mcf();
86     printf("%.2lf",ans/n);
87     return 0;
88 }

显然zkw快的多，正好填了zkw的大坑

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 using namespace std;
  6 
  7 const int INF=0x7f7f7f7f;
  8 const int T=1001;
  9 
 10 struct Edge
 11 {
 12     int from,to,v,c,next;
 13 }E[1000000];
 14 int node=1;
 15 int head[5000],dis[5000];
 16 bool vis[5000];
 17 
 18 int n,m;
 19 double ans;
 20 int t[61][10];
 21 
 22 void ins(int from,int to,int v,int c)
 23 {
 24     E[++node]=(Edge){from,to,v,c,head[from]};
 25     head[from]=node;
 26 }
 27 void insert(int from,int to,int v,int c)
 28 {
 29     ins(from,to,v,c);ins(to,from,0,-c);
 30 }
 31 
 32 bool spfa()
 33 {
 34     memset(vis,0,sizeof(vis));
 35     memset(dis,0x7f,sizeof(dis));
 36     queue<int> Q;
 37     Q.push(T);
 38     dis[T]=0;vis[T]=1;
 39     while(!Q.empty())
 40     {
 41         int q=Q.front();Q.pop();
 42         for(int i=head[q];i;i=E[i].next)
 43             if(E[i^1].v&&dis[q]-E[i].c<dis[E[i].to])
 44             {
 45                 dis[E[i].to]=dis[q]-E[i].c;
 46                 if(!vis[E[i].to])
 47                 {
 48                     vis[E[i].to]=1;
 49                     Q.push(E[i].to);
 50                 }
 51             }
 52         vis[q]=0;
 53     }
 54     return dis[0]!=INF;
 55 }
 56 
 57 int dfs(int x,int f)
 58 {
 59     if(x==T) return f;
 60     int w,used=0;
 61     vis[x]=1;
 62     for(int i=head[x];i;i=E[i].next)
 63         if(!vis[E[i].to]&&E[i].v&&dis[E[i].to]==dis[x]-E[i].c)
 64         {
 65             w=f-used;
 66             w=dfs(E[i].to,min(w,E[i].v));
 67             ans+=w*E[i].c;
 68             E[i].v-=w;E[i^1].v+=w;
 69             used+=w;
 70             if(used==f) return f;
 71         }
 72     return used;
 73 }
 74 
 75 void zkw()
 76 {
 77     while(spfa())
 78     {
 79         vis[T]=1;
 80         while(vis[T])
 81         {
 82             memset(vis,0,sizeof(vis));
 83             dfs(0,INF);
 84         }
 85     }
 86 }
 87 
 88 int main()
 89 {
 90     scanf("%d %d",&m,&n);
 91     for(int i=1;i<=n;i++)
 92         for(int j=1;j<=m;j++)
 93             scanf("%d",&t[i][j]);
 94     for(int i=1;i<=n*m;i++)
 95         insert(0,i,1,0);
 96     for(int i=n*m+1;i<=n*m+n;i++)
 97         insert(i,T,1,0);
 98     for(int i=1;i<=m;i++)
 99         for(int j=1;j<=n;j++)
100             for(int k=1;k<=n;k++)
101                 insert((i-1)*n+j,n*m+k,1,t[k][i]*j);
102     zkw();
103     printf("%.2lf",ans/n);
104     return 0;
105 }