HDU5619 （费用流）

Problem Jam's Store (HDU5619)

题目大意

　　有m个服务员，和n个顾客，给出每个服务员招待每个顾客的时间，每个服务员在同一时间只能服务一个顾客，询问所有顾客完成服务的最少时间。

解题分析

　　第一反应就是用费用流来做。

　　题目难度在于每个服务员在同一时间只能服务一个顾客。考虑把每个服务员拆成n个点，表示服务员的服务顺序。

　　若第i个顾客是第j个服务员的倒数第k个服务对象，那么对答案的贡献为V[i,j]*k （使k-1个顾客等待了V[i,j]的时间）

　　因此由S向每个顾客连一条(1,0)的边，第i个顾客向第j个服务员的第k个点连一条（1，v[i,j]*k）的边，每个服务员的n个点向T’连一条（1,0）的边，T'向T连一条（n,0）的边。

参考程序

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 using namespace std;
 6 
 7 #define V 1008
 8 #define E 1000008
 9 #define INF 200000000
10 int n,m,S,T,Que;
11 
12 int pd[V],dis[V],pre[V];
13 struct line{
14     int u,v,c,w,nt;
15 }eg[E];
16 int lt[V],sum;
17 
18 void adt(int u,int v,int c,int w) {
19     eg[++sum].u=u; eg[sum].v=v; eg[sum].c=c; 
20     eg[sum].w=w; eg[sum].nt=lt[u]; lt[u]=sum;
21 }
22 
23 void add(int u,int v,int c,int w) {
24     adt(u,v,c,w); adt(v,u,0,-w);
25     //printf("%d %d %d %d
",u,v,c,w);
26 }
27 
28 void init(){
29 
30     sum=1;
31     memset(lt,0,sizeof(lt));
32     scanf("%d%d",&m,&n);
33     S = 0; T = (m+1)*n+2;
34     for (int i=1;i<=n;i++) add(S,i,1,0);
35     for (int i=1;i<=n;i++) 
36         for (int j=1;j<=m;j++) {
37             int x;
38             scanf("%d",&x);
39             for (int k=1;k<=n;k++) 
40                 add(i,j*n+k,1,k*x);
41         }
42     for (int i=n+1;i<=(m+1)*n;i++) 
43         add(i,T-1,1,0);
44     add(T-1,T,n,0);
45     n=T;
46 }
47 
48 bool spfa() {
49     queue <int> Q;
50     for (int i=0;i<=n;i++) {
51         dis[i]=INF;
52         pd[i]=0;
53         pre[i]=-1;
54     }
55     dis[S]=0; pd[S]=1; Q.push(S);
56     while (!Q.empty()) {
57         int u = Q.front();
58         for (int i=lt[u];i;i=eg[i].nt) 
59             if (eg[i].c>0) {
60                 int v=eg[i].v;
61                 if (dis[u]+eg[i].w<dis[v]) {
62                     dis[v]=dis[u]+eg[i].w;
63                     pre[v]=i;
64                     if (!pd[v]) {
65                         Q.push(v);
66                         pd[v]=1;
67                     }
68                 }
69             }
70         pd[u]=0;
71         Q.pop();
72     }
73     return dis[T]!=INF;
74 }
75 
76 void minCmaxF(){
77     int minC=0,maxF=0,flow;
78     while (spfa()) {
79         flow=INF;
80         for (int i=pre[T];~i;i=pre[eg[i].u])
81             flow=min(flow,eg[i].c);
82         for (int i=pre[T];~i;i=pre[eg[i].u]) {
83             eg[i].c-=flow;
84             eg[i^1].c+=flow;
85         }
86         maxF+=flow;
87         minC+=flow*dis[T];
88     }
89     printf("%d
",minC);
90 
91 }
92 
93 int main(){
94     scanf("%d",&Que);
95     while (Que--) {
96         init();
97         minCmaxF();
98     }
99 }

View Code