「NOI2012」美食节 - 费用流+流量分配+拆点

题目大意

    CZ市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。作为一个喜欢尝鲜的美食客，小M自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小M仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小M开始研究起了做菜顺序的问题，即安排一个做菜的顺序使得同学们的等待时间最短。小M发现，美食节共有$n$种不同的菜品。每次点餐，每个同学可以选择其中的一个菜品。总共有$m$个厨师来制作这些菜品。当所有的同学点餐结束后，菜品的制作任务就会分配给每个厨师。然后每个厨师就会同时开始做菜。厨师们会按照要求的顺序进行制作，并且每次只能制作一人份。此外，小M还发现了另一件有意思的事情: 虽然这m个厨师都会制作全部的$n$种菜品，但对于同一菜品，不同厨师的制作时间未必相同。他将菜品用$1,2,\ldots,n$依次编号，厨师用$1,2,\ldots,m$依次编号，将第$j$个厨师制作第$i$种菜品的时间记为$t_{ij}$。小M认为：每个同学的等待时间为所有厨师开始做菜起，到自己那份菜品完成为止的时间总长度。换句话说，如果一个同学点的菜是某个厨师做的第$k$道菜，则他的等待时间就是这个厨师制作前$k$道菜的时间之和。而总等待时间为所有同学的等待时间之和。现在，小M找到了所有同学的点菜信息: 有$p_i$个同学点了第$i$种菜品（$i=1,2,\ldots,n$）。他想知道的是最小的总等待时间是多少。

---

题目分析

和修车类似。
直接用修车的建模可以拿$60$分。
改为动态加点，就可以A了。
动态加点的意思是，每次厨师做了一道菜，再把后一道菜加进去。
也就是添加新的上一次增广的点。
这样可以使网络流图变小，加快时间。

当然此题写多路增广就麻烦了，要加很多边，因此直接上EK。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits> 
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=100005;

struct Edge {
	int from,to,cap,flow;
	LL cost;
	Edge(int x=0,int y=0,int c=0,int f=0,LL co=0):from(x),to(y),cap(c),flow(f),cost(co) {}
};

int n,m,p[45],map[45][105],sum=0;

int id(int j,int k) {
	return n+(j-1)*sum+k;
}

struct MinimumCost_MaximumFlow { //EK Edition
	int n,m,A,B;
	vector<Edge>edges;
	vector<int>G[maxn];
	bool inque[maxn];
	int a[maxn],path[maxn];
	LL dist[maxn];
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	void AddEdge(int x,int y,int v,LL f) {
		edges.push_back(Edge(x,y,v,0,f));
		edges.push_back(Edge(y,x,0,0,-f));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
	}
	bool bellmanford(int n,int s,int t,int& flow,LL& cost) {
		for(int i=1; i<=this->n; i++)dist[i]=LLONG_MAX/2;
		memset(inque,0,sizeof(inque));
		queue<int>Q;
		Q.push(s);
		dist[s]=path[s]=0;
		a[s]=INT_MAX;
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop();
			inque[Now]=0;
			for(int id:G[Now]) {
				Edge& e=edges[id];
				int Next=e.to;
				if(e.cap>e.flow&&dist[Next]>dist[Now]+e.cost) {
					dist[Next]=dist[Now]+e.cost;
					path[Next]=id;
					a[Next]=min(a[Now],e.cap-e.flow);
					if(!inque[Next]) {
						Q.push(Next);
						inque[Next]=1;
					}
				}
			}
		}
		if(dist[t]==LLONG_MAX/2)return false;
		flow+=a[t];
		cost+=dist[t]*a[t];
		for(int Now=t; Now!=s; Now=edges[path[Now]].from) {
			if(edges[path[Now]].to==t) {
				int tmp=edges[path[Now]].from;
				B=(tmp-n)%sum+1;
				A=(tmp-n-B+1)/sum+1;
			}
			edges[path[Now]].flow+=a[t];
			edges[path[Now]^1].flow-=a[t];
		}
		return true;
	}
	int maxflow(int n,int s,int t,LL& cost) {
		int flow=0;
		cost=0;
		while(bellmanford(n,s,t,flow,cost))
			for(int i=1; i<=n; i++)AddEdge(i,id(A,B),1,B*map[i][A]); //动态加边;
		return flow;
	}
} mcmf;

int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++)p[i]=Get_Int(),sum+=p[i];
	int S=m*sum+n+1,T=m*sum+n+2;
	mcmf.init(T);
	for(int i=1; i<=n; i++)mcmf.AddEdge(S,i,p[i],0);
	for(int i=1; i<=m*sum; i++)mcmf.AddEdge(n+i,T,1,0); //总共将厨师拆成sum个点
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			map[i][j]=Get_Int();
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			mcmf.AddEdge(i,id(j,1),1,map[i][j]);
	LL cost=0;
	mcmf.maxflow(n,S,T,cost);
	printf("%lld\n",cost);
	return 0;
}