HDU5619 Jam's store（最小费用最大流 MCMF）

2019-11-10 19:08:58

字体：大中小

来源：转载

供稿：网友

题意

n个顾客m个服务员，给出每个服务员给每个顾客服务需要的时间，求顾客最小的等待时间

建图

网络流真是玄学啊，就是不会建图。。

源点向每个客户连边，控制流量为n服务员拆点，每个客户向每个服务员连n条边，表示是该服务员倒数第k个服务的对象，代价为k*cost[i] [j]拆点后的服务员向汇点连边

因此每个服务员会先确定最后一个服务的对象

代码

#include <bits/stdc++.h>#define mem(a,b) memset(a,b,sizeof(a))#define rep(i,a,b) for(int i=a;i<b;i++)#define debug(a) PRintf("a =: %d/n",a);#define sc(x) scanf("%d",&x)const int INF=0x3f3f3f3f;const int maxn=500+50;const int Mod=1000000007;const double PI=acos(-1);typedef long long ll;typedef unsigned int ui;using namespace std;struct Edge{ int from,to,cap,flow,cost; Edge() {} Edge(int from, int to, int cap, int flow, int cost) : from(from), to(to), cap(cap), flow(flow), cost(cost) {}};struct MCMF{ int m; vector<Edge> edges; vector<int> G[maxn]; int inq[maxn]; int d[maxn]; int p[maxn]; int a[maxn]; void init(int n){ for(int i=0;i<=n;i++) G[i].clear(); edges.clear(); } void addEdge(int from,int to,int cap,int cost){ edges.push_back(Edge(from,to,cap,0,cost)); edges.push_back(Edge(to,from,0,0,-cost)); m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool spfa(int s,int t,int &flow,int &cost){ mem(d,0x3f); mem(inq,0); mem(a,0); d[s]=0; inq[s]=1; p[s]=0; a[s]=INF; queue<int> qu; qu.push(s); while(!qu.empty()){ int u=qu.front(); qu.pop(); inq[u]=0; int sz=G[u].size(); for(int i=0;i<sz;i++){ Edge &edge=edges[G[u][i]]; if(edge.cap>edge.flow && d[edge.to]>d[u]+edge.cost){ d[edge.to]=d[u]+edge.cost; p[edge.to]=G[u][i]; a[edge.to]=min(a[u],edge.cap-edge.flow); if(!inq[edge.to]){ qu.push(edge.to); inq[edge.to]=1; } } } } if(d[t]==INF) return false; flow+=a[t]; cost+=d[t]*a[t]; int u=t; while(u!=s){ edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; u=edges[p[u]].from; } return true; } int minCost(int s,int t){ int flow=0,cost=0; while(spfa(s,t,flow,cost)); //cout<<"flow "<<flow<<endl; return cost; }};int s[233][233];MCMF mcmf;int main(){#ifndef ONLINE_JUDGE //freopen("/home/martin/ClionProjects/untitled/in.txt","r",stdin); //freopen("/home/martin/ClionProjects/untitled/out.txt","w",stdout);#endif int T; scanf("%d",&T); for(int cs=1;cs<=T;cs++){ int n,m; scanf("%d %d",&m,&n); //scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&s[i][j]); int N=1+n+n*m; mcmf.init(N+1); for(int i=1;i<=n;i++) mcmf.addEdge(0,i,1,0); for(int j=1;j<=m;j++) for(int i=1;i<=n;i++){ for(int k=1;k<=n;k++){ mcmf.addEdge(i,j*n+k,1,k*s[i][j]); } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mcmf.addEdge(j*n+i,N,1,0); printf("%d/n",mcmf.minCost(0,N)); //printf("Case #%d: %d/n",cs,mcmf.minCost(0,N)); } return 0;}

上一篇：好久不见 Lua

下一篇：最小生成树若干性质以及在ACM中的应用