\(\mathcal{Descriptoin}\)

Link.

你有一个容量为 \(k\) 的空书架，现在共有 \(n\) 个请求，每个请求给定一本书 \(a_i\)。如果你的书架里没有这本书，你就必须以 \(c_{a_i}\) 的价格购买这本书放入书架。当然，你可以在任何时候丢掉书架里的某本书。请求出完成这 \(n\) 个请求所需要的最少价钱。

\(n,k\le80\)。

\(\mathcal{Solution}\)

网络瘤嘛……

费用流，考虑先全部买入，再抵消花费。具体地，假设 \(i<j\)，第 \(i\) 天的书和第 \(j\) 天的书相同，就可以一直保留第 \(i\) 天的书到第 \(j\) 天，减少一次花费。脑洞一番之后，建图如下：

\(S\) 向 \(v_i~(i=1,2,\dots n)\) 连边，容量为 \(1\)，费用为 \(c_{a_i}\)，表示买入。
\(v_i\) 向 \(v_{i+1}~(i=1,2,\cdots,n-1)\) 连边，容量为 \(k-1\)，费用为 \(0\)，表示保留至多 \(k-1\) 本，剩下一本给 \(a_{i+1}\) 留位置。
\(v_i\) 向 \(v_i'~(i=1,2,\cdots,n)\) 连边，容量为 \(1\)，费用为 \(0\)，表示将这本书出手（丢掉或卖掉）。
\(v_{i-1}\) 向上一次 \(a_i\) 出现的位置 \(j\) 所对应的 \(v_j'\) 连边，容量为 \(1\)，费用为 \(-c_{a_i}\)，表示上次的“出手”是卖掉，以抵消本次 \(a_i\) 的花费。
\(v_i'\) 向 \(T\) 连边，容量为 \(1\)，费用为 \(0\)。

费用流求出的最小费用就是答案。

\(\mathcal{Code}\)

#include <queue>

#include <cstdio>

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

const int MAXN = 80, MAXND = MAXN * 2 + 2, MAXED = 5 * MAXN, INF = 0x3f3f3f3f;

int n, K, S, T, ecnt = 1, a[MAXN + 5], c[MAXN + 5], las[MAXN + 5];

int head[MAXND + 5], curh[MAXND + 5], d[MAXND + 5];

bool vis[MAXND + 5];

struct Edge { int to, flow, cost, nxt; } graph[MAXED * 2 + 5];

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

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

	head[s] = ecnt;

}

inline void addEdge ( const int s, const int t, const int f, const int c ) {

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

}

inline pii DFS ( const int u, int iflow ) {

	vis[u] = true;

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

	int oflow = 0, ocost = 0;

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

		if ( ! vis[v = graph[i].to] && d[v] == d[u] + graph[i].cost && graph[i].flow ) {

			pii of ( DFS ( v, std::min ( iflow, graph[i].flow ) ) );

			oflow += of.first, ocost += of.first * graph[i].cost + of.second;

			graph[i].flow -= of.first, graph[i ^ 1].flow += of.first;

			if ( ! ( iflow -= of.first ) ) break;

		}

	}

	if ( ! oflow ) d[u] = INF;

	return { oflow, ocost };

}

inline bool SPFA () {

	static std::queue<int> que;

	static bool inq[MAXND + 5];

	for ( int i = 0; i <= T; ++ i ) d[i] = INF, inq[i] = false;

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

	for ( int u; ! que.empty (); ) {

		inq[u = que.front ()] = false, que.pop ();

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

			if ( d[v = graph[i].to] > d[u] + graph[i].cost && graph[i].flow ) {

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

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

			}

		}

	}

	return d[T] ^ INF;

}

inline int Dinic () {

	int ret = 0;

	for ( ; SPFA (); ret += DFS ( S, INF ).second ) {

		for ( int i = 0; i <= T; ++ i ) {

			vis[i] = false;

			curh[i] = head[i];

		}

	}

	return ret;

}

int main () {

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

	for ( int i = 1; i <= n; ++ i ) scanf ( "%d", &a[i] );

	for ( int i = 1; i <= n; ++ i ) scanf ( "%d", &c[i] );

	S = 0, T = n << 1 | 1;

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

		addEdge ( S, i, 1, c[a[i]] ), addEdge ( i, i + n, 1, 0 );

		if ( las[a[i]] ) addEdge ( i - 1, las[a[i]] + n, 1, -c[a[i]] );

		if ( i < n ) addEdge ( i, i + 1, K - 1, 0 );

		addEdge ( i + n, T, 1, 0 ), las[a[i]] = i;

	}

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

	return 0;

}

巴特西

Solution -「CF 802C」Heidi and Library (hard)

\(\mathcal{Descriptoin}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章