[BZOJ1070]修车

题目链接

题目大意为:有$n$个人一起去洗车,洗车店有$m$个员工,给你一个$n*m$的矩阵,$a[i][j]$表示第$j$个员工洗第$i$辆车的时间,问最少的平均等待时间为多少(等待时间为从进店开始直到洗车完毕的时间)。

费用流的题目,难点就在于建图。

对于每一辆车$i$,假设它是第$j$个人洗的倒数第$k$辆车,那么之后的那$k-1$辆都需要等待$a[i][j]$的时间,加上它本身的话,那么洗这辆车的总等待时间就为$a[i][j]*k$,我们以此建图,跑一个费用流即可。

首先我们要建立一个超级源点$S$和超级汇点$T$,作为网络流的起点和终点。然后将$S$与$n*m$个节点相连,将$n$个节点与$T$相连,然后我们开始链接中间的$n*m*n$条边。对于每条边,我们要明确知道提所代表的含义(这点很重要!!!否则你建的图不可能是正确的)。
先看我们之前的那句话“第$j$个人倒数第$k$个洗第$i$辆车的等待时间为$a[i][j]*k$”,那么在我们新建立的$n*m+n$中,右边的$n$个节点代表每辆车;左边的$n*m$个节点代表第$j$个人洗的倒数第$k$辆车。那么我们就能建立起每条边了:

1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=1;k<=n;k++){
//id[k][j]表示左边n*m个节点的编号,也即(第j个人洗倒数第k辆车)所对应的编号
//id2[i]表示右边n个节点的编号,也即第i辆车所对应的编号
//两者进行结合即为上面一段的那句话
add(id[k][j],id2[i],1,a[i][j]*k);
add(id2[i],id[k][j],0,-a[i][j]*k);
}
}
}

建完图后其他步骤和费用流一样。完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
const int INF=0x3f3f3f3f;
const int maxn=100000+10;
struct node{
int to,nxt,cost,flow;
}e[maxn];
int a[100][100];
int id[100][100],id2[100];
int dis[maxn],vis[maxn];
int head[maxn],cur[maxn];
int n,m,cnt=1,S,T,res,point=0;
void add(int u,int v,int w,int c){
e[++cnt].to=v;
e[cnt].flow=w;
e[cnt].cost=c;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void init(){
S=++point;
T=++point;
for(int i=1;i<=n;i++){
add(id2[i]=++point,T,1,0);
add(T,id2[i],0,0);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
add(S,id[i][j]=++point,1,0);
add(id[i][j],S,0,0);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=1;k<=n;k++){
add(id[k][j],id2[i],1,a[i][j]*k);
add(id2[i],id[k][j],0,-a[i][j]*k);
}
}
}
}
bool spfa(int s,int t){
memset(vis,0,sizeof(vis));
memset(dis,INF,sizeof(dis));
queue<int>que;
que.push(s);
dis[s]=0;
vis[s]=1;
while(!que.empty()){
int u=que.front();
que.pop();
vis[u]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
int w=e[i].cost;
if(e[i].flow && dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if(!vis[v]){
que.push(v);
vis[v]=1;
}
}
}
}
return dis[t]!=INF;
}
int dfs(int u,int t,int flow){
if(u==t) return flow;
vis[u]=1;
int ans=0;
for(int &i=cur[u];i && ans<flow;i=e[i].nxt){
int v=e[i].to;
int w=e[i].cost;
if(!vis[v] && e[i].flow && dis[v]==dis[u]+w){
int x=dfs(v,t,min(flow-ans,e[i].flow));
if(x){
res+=x*w;
e[i].flow-=x;
e[i^1].flow+=x;
ans+=x;
}
}
}
vis[u]=0;
return ans;
}
void mcmf(){
int x;
while(spfa(S,T)){
memcpy(cur,head,sizeof(head));
while(x=dfs(S,T,1));
}
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d %d",&m,&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
init();
mcmf();
printf("%.2lf\n",1.0*res/n);
return 0;
}
感谢您的支持
-------------本文结束感谢您的阅读-------------