\(\mathcal{Description}\)

Link.

美食节提供 \(n\) 种菜品，第 \(i\) 种的需求量是 \(p_i\)，菜品由 \(m\) 个厨师负责制作，第 \(j\) 个厨师做第 \(i\) 道菜的用时是 \(t_{ij}\)。安排做菜方案，使得 \(\sum p_i\) 个需求等待的总时间最小。

\(n\le40\)，\(m\le100\)，\(\sum p_i\le800\)。

\(\mathcal{Solution}\)

对于每个厨师，他做他所负责的倒数第 \(i\) 道菜的额外贡献系数为 \(i\)，即其对答案贡献 \(i\times\) 做该道菜的用时。所以想到已时间为层建分层图，菜品令为 \(d_1,d_2,\cdots,d_n\)，第 \(i\) 个厨师拆为 \(i_1,i_2,\cdots,i_n\)，表示做倒数第 \(1\) 道菜的 \(i\) 厨师，做倒数第二道菜的 \(i\) 厨师，……，做倒数第 \(n\) 道菜的 \(i\) 厨师。每个 \(d_k\) 向 \(i_j\) 连一条费用为 \(jt_{ki}\) 的边，其余边自行脑补，跑最小费用最大流即可。

然而 \(\mathcal O(\operatorname{Dinic}(nm,n^2m))\) 并跑不过，需要用动态加点的优化方法：当某个厨师用到了 \(i_j\) 这一虚点时，再加入 \(i_{j+1}\) 及其连边。

\(\mathcal{Code}\)

/* Clearink */

#include <queue>

#include <cstdio>

#include <cassert>

#include <algorithm>

#define rep( i, l, r ) for ( int i = l, repEnd##i = r; i <= repEnd##i; ++i )

#define per( i, r, l ) for ( int i = r, repEnd##i = l; i >= repEnd##i; --i )

typedef std::pair<int, int> PII;

inline int rint () {

	int x = 0; char s = getchar ();

	for ( ; s < '0' || '9' < s; s = getchar () );

	for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );

	return x;

}

inline int imin ( const int a, const int b ) { return a < b ? a : b; }

const int MAXN = 40, MAXM = 100, MAXND = 1e4, INF = 0x3f3f3f3f;

int n, m, cook[MAXN + 5][MAXM + 5], bel[MAXND + 5], stp[MAXM + 5], vis[MAXND + 5];

struct MaxFlowCostGraph {

	static const int MAXND = ::MAXND, MAXEG = 2e6;

	int ecnt, head[MAXND + 5], S, T, bound, curh[MAXND + 5], d[MAXND + 5];

	bool inq[MAXND + 5];

	struct Edge { int to, flw, cst, nxt; } graph[MAXEG * 2 + 5];

	MaxFlowCostGraph (): ecnt ( 1 ) {}

	inline void link ( const int s, const int t, const int f, const int w ) {

		graph[++ecnt] = { t, f, w, head[s] };

		head[s] = ecnt;

	}

	inline Edge& operator [] ( const int k ) { return graph[k]; }

	inline void operator () ( const int s, const int t, const int f, const int w ) {

		#ifdef RYBY

			printf ( "%d %d ", s, t );

			if ( f == INF ) printf ( "INF " );

			else printf ( "%d ", f );

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

		#endif

		link ( s, t, f, w ), link ( t, s, 0, -w );

	}

	inline bool spfa () {

		static std::queue<int> que;

		for ( int i = 0; i <= bound; ++i ) d[i] = -1, inq[i] = false;

		d[S] = 0, inq[S] = true, que.push ( S );

		while ( !que.empty () ) {

			int u = que.front (); que.pop ();

			inq[u] = false;

			for ( int i = head[u], v; i; i = graph[i].nxt ) {

				if ( graph[i].flw

				&& ( !~d[v = graph[i].to] || d[v] > d[u] + graph[i].cst ) ) {

					d[v] = d[u] + graph[i].cst;

					if ( !inq[v] ) que.push ( v ), inq[v] = true;

				}

			}

		}

		return ~d[T];

	}

	inline PII dfs ( const int u, const int iflw ) {

		if ( u == T ) return { iflw, 0 };

		inq[u] = true; PII ret ( 0, 0 );

		for ( int& i = curh[u], v; i; i = graph[i].nxt ) {

			if ( graph[i].flw && !inq[v = graph[i].to]

			&& d[v] == d[u] + graph[i].cst ) {

				PII oflw ( dfs ( v, imin ( iflw - ret.first, graph[i].flw ) ) );

				graph[i].flw -= oflw.first, graph[i ^ 1].flw += oflw.first;

				ret.first += oflw.first;

				ret.second += graph[i].cst * oflw.first + oflw.second;

				if ( ret.first == iflw ) break;

			}

		}

		if ( !ret.first ) d[u] = -1;

		return inq[u] = false, ret;

	}

} graph;

int main () {

	n = rint (), m = rint ();

	int S = 0, T = graph.bound = 1e4, cnt = n;

	rep ( i, 1, n ) graph ( S, i, rint (), 0 );

	rep ( i, 1, n ) rep ( j, 1, m ) cook[i][j] = rint ();

	rep ( i, 1, m ) {

		graph ( ++cnt, T, 1, 0 ), bel[cnt] = i, stp[i] = 1;

		rep ( j, 1, n ) graph ( j, cnt, 1, cook[j][i] );

	}

	graph.S = S, graph.T = T;

	int ans = 0;

	while ( graph.spfa () ) {

		for ( int i = 0; i <= graph.bound; ++i ) {

			graph.inq[i] = false, graph.curh[i] = graph.head[i];

		}

		ans += graph.dfs ( S, INF ).second;

		for ( int i = graph.head[T], v, cid; i; i = graph[i].nxt ) {

			if ( graph[i].flw && !vis[v = graph[i].to] ) {

				vis[v] = true, cid = bel[v];

				graph ( ++cnt, T, 1, 0 ), ++stp[bel[cnt] = cid];

				rep ( j, 1, n ) graph ( j, cnt, 1, stp[cid] * cook[j][cid] );

			}

		}

	}

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

	return 0;

}

巴特西

Solution -「NOI 2012」「洛谷 P2050」美食节

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章