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）的边。

参考程序

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 using namespace std;

 #define V 1008

 #define E 1000008

 #define INF 200000000

 int n,m,S,T,Que;

 int pd[V],dis[V],pre[V];

 struct line{

     int u,v,c,w,nt;

 }eg[E];

 int lt[V],sum;

 void adt(int u,int v,int c,int w) {

     eg[++sum].u=u; eg[sum].v=v; eg[sum].c=c;

     eg[sum].w=w; eg[sum].nt=lt[u]; lt[u]=sum;

 }

 void add(int u,int v,int c,int w) {

     adt(u,v,c,w); adt(v,u,,-w);

     //printf("%d %d %d %d\n",u,v,c,w);

 }

 void init(){

     sum=;

     memset(lt,,sizeof(lt));

     scanf("%d%d",&m,&n);

     S = ; T = (m+)*n+;

     for (int i=;i<=n;i++) add(S,i,,);

     for (int i=;i<=n;i++)

         for (int j=;j<=m;j++) {

             int x;

             scanf("%d",&x);

             for (int k=;k<=n;k++)

                 add(i,j*n+k,,k*x);

         }

     for (int i=n+;i<=(m+)*n;i++)

         add(i,T-,,);

     add(T-,T,n,);

     n=T;

 }

 bool spfa() {

     queue <int> Q;

     for (int i=;i<=n;i++) {

         dis[i]=INF;

         pd[i]=;

         pre[i]=-;

     }

     dis[S]=; pd[S]=; Q.push(S);

     while (!Q.empty()) {

         int u = Q.front();

         for (int i=lt[u];i;i=eg[i].nt)

             if (eg[i].c>) {

                 int v=eg[i].v;

                 if (dis[u]+eg[i].w<dis[v]) {

                     dis[v]=dis[u]+eg[i].w;

                     pre[v]=i;

                     if (!pd[v]) {

                         Q.push(v);

                         pd[v]=;

                     }

                 }

             }

         pd[u]=;

         Q.pop();

     }

     return dis[T]!=INF;

 }

 void minCmaxF(){

     int minC=,maxF=,flow;

     while (spfa()) {

         flow=INF;

         for (int i=pre[T];~i;i=pre[eg[i].u])

             flow=min(flow,eg[i].c);

         for (int i=pre[T];~i;i=pre[eg[i].u]) {

             eg[i].c-=flow;

             eg[i^].c+=flow;

         }

         maxF+=flow;

         minC+=flow*dis[T];

     }

     printf("%d\n",minC);

 }

 int main(){

     scanf("%d",&Que);

     while (Que--) {

         init();

         minCmaxF();

     }

 }

巴特西

HDU5619 （费用流）

最新文章

热门文章