HDU5619 – Jam’s store(费用流)

题目链接

【题意】：Jam不好好学习，然后就去帮别人修电脑了，在一家店里，有M个店员，现在有N个顾客，给出每个顾客对应给每个店员的修电脑的时间为Tij，问所有顾客要等待的最少时间。当然，一个顾客在某个店员那里完成之后，那个店员才会执行下一个顾客的任务

【分析】由于每个店员同时只能接待一个顾客， 而顾客数量N只有20，所以可以把每个店员拆点，拆成N个点P[i,j,k]，表示j号店员倒数第k个接待顾客i。而对于每个店员倒数第一个顾客的接待时间是不会影响任何人了，所以因为他产生的时间为1*T[i][j]，而倒数第二个接待的时间会影响倒数第一人，而总时间为倒数第一个人自己消耗的时间1*T[i][j]+倒数第二个人消耗的时间以及影响倒数第一个人的时间和2*T[i][j],这样倒数第n个增加的时间为n*T[i][j]。

这样就把M个店员拆成M*N个点，然后虚拟源点0向N个顾客各连一条费用0流量1的边(限制总流量为N)，然后每个顾客连向每个店员在倒数第K个时的费用为K*T[i][j]流量为1的边。最后每个店员拆完点后的N*M个点连向虚拟汇点流量1费用0的边。这样求最小费用流就是所有顾客都完成后的最小时间花费。

【AC CODE】93ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 400+20+10, MAXM = 20*20*20+20+20*20+10;
struct ZKW_MinCostMaxFlow
{
private:
	int st, ed, ecnt, n;
	int head[MAXN],cap[MAXM<<1],cost[MAXM<<1],to[MAXM<<1],nxt[MAXM<<1];//有反向边，记得两倍
	int dis[MAXN];
	void SPFA()
	{
		repe(i,0,n) dis[i] = INF;
		priority_queue<pair<int, int> > q;
		dis[st] = 0;
		q.push(make_pair(0, st));
		while(!q.empty()){
			int u = q.top().second, d = -q.top().first;
			q.pop();
			if(dis[u] != d) continue;
			for(int p = head[u]; p!=-1; p = nxt[p]){
				int &v = to[p];
				if(cap[p] && dis[v] > d + cost[p]){
					dis[v] = d + cost[p];
					q.push(make_pair(-dis[v], v));
				}
			}
		}
		repe(i,0,n) dis[i] = dis[ed] - dis[i];
	}
	int minCost, maxFlow;
	bool use[MAXN];
	int add_flow(int u, int flow)
	{
		if(u == ed)
		{
			maxFlow += flow;
			minCost += dis[st] * flow;
			return flow;
		}
		use[u] = true;
		int now = flow;
		for(int p = head[u]; p!=-1; p = nxt[p])
		{
			int &v = to[p];
			if(cap[p] && !use[v] && dis[u] == dis[v] + cost[p])
			{
				int tmp = add_flow(v, min(now, cap[p]));
				cap[p] -= tmp;
				cap[p^1] += tmp;
				now -= tmp;
				if(!now) break;
			}
		}
		return flow - now;
	}
	bool modify_label()
	{
		int d = INF;
		repe(u,0,n) if(use[u])
			for(int p = head[u]; p!=-1; p = nxt[p])
			{
				int &v = to[p];
				if(cap[p] && !use[v]) d = min(d, dis[v] + cost[p] - dis[u]);
			}
		if(d == INF) return false;
		repe(i,0,n) if(use[i]) dis[i] += d;
		return true;
	}
public:
	void init()
	{
		clc(head,-1);
		ecnt = 2;
	}
	void add_edge(int u, int v, int cc, int ww)//点u-v,cc-容量,ww-单位流量费用
	{
		cap[ecnt] = cc; cost[ecnt] = ww; to[ecnt] = v;
		nxt[ecnt] = head[u]; head[u] = ecnt++;
		cap[ecnt] = 0; cost[ecnt] = -ww; to[ecnt] = u;
		nxt[ecnt] = head[v]; head[v] = ecnt++;
	}
	int zkw(int ss, int tt, int nn, int &flow)//ss-源点，tt-汇点,nn-点的总数(编号0~n)
	{
		st = ss, ed = tt, n = nn;
		minCost = maxFlow = 0;
		SPFA();
		while(true)
		{
			while(true)
			{
				repe(i,0,n) use[i] = 0;
				if(!add_flow(st, INF)) break;
			}
			if(!modify_label()) break;
		}
		flow = maxFlow;
		return minCost;
	}
}zkwflow;
int cost[30][30];

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int n,m;
		scanf("%d%d", &m,&n);
		repe(i,1,n)
		{
			repe(j,1,m)
			{
				scanf("%d", &cost[i][j]);
			}
		}
		zkwflow.init();
		repe(i,1,n)
		{
			zkwflow.add_edge(0,i,1,0);
			repe(j,1,m)
			{
				repe(k,1,n)
				{
					zkwflow.add_edge(i,(j-1)*n+k+n,1,k*cost[i][j]);
				}
			}
		}
		int ed = (m-1)*n+n+n+1;
		repe(j,1,m)
		{
			repe(k,1,n)
			{
				zkwflow.add_edge((j-1)*n+k+n,ed,1,0);
			}
		}
		int flow;
		printf("%d\n", zkwflow.zkw(0,ed,2+n+m*n,flow));
	}
	return 0;
}