AOJ 2266 Cache Strategy 题解 《挑战程序设计竞赛》

AOJ 2266 Cache Strategy

擦车策略：Google Code Jam区域赛上，坐在右前方的男人ID叫lyrically。东京大学时代的记忆中，记得有个朋友也用类似的ID。不过我的朋友都是萌妹子，我记忆中的lyrically不仅算法扎实，封装也很强，能一下子给出问题的正解。比如，对我们写得不好的程序也能优化到AC的程度。她说，程序优化时，对缓存池的利用特别重要。

那么问题来了，现在请你优化下面的缓存池模型：

有M个桶，N个球，球编号为1到N，每个球都有重量w_i。然后给出一个长K的数列，数列由球的编号构成。开始的时候，桶都是空的。接着我们从前往后从数列中取出一个数a_j，执行如下操作：

如果球a_j已经存在于某一个桶中，那么什么也不干，花费为0，继续。

如果任何桶中都没有a_j，那么找一个桶放a_j，如果该桶里还有球，那么取出原来的球，将a_j放进去。这种操作的花费是a_j的重量w_a_j，与桶以及原来的球没关系。

求最小花费？

题目数据第一行是M N K，接着N行权重，K行编号。

3.5借助水流解决问题的网络流 

最小费用流 

第一段跟题目根本就没啥关系吧你一个理工男的朋友都是萌妹子谁信啊，总之这段话我原封不动地翻译过来了。

不过题目真心难，看osak的代码都看了好久才大概明白是怎么回事。大概的思路是先考虑最坏情况=每次都拿出来放进去，接着看怎么省。已经在桶里的球在下一个相同编号到来的时候就不用花费了，以每个时刻的状态为顶点，放了球的桶的状态到下一个相同编号来临的桶的状态建立一条负权边，cost=-w_a_j，cap=1，当然空桶可以无限次转移，cost=0，cap=∞。又因为至少有个桶是非空的，所以取流量F=M-1，新增源汇点，跑最小费用流，这是个负数，加上上面说的求和，就是答案。

osak用了一个primal dual算法，封装得简直美轮美奂……

深受打击……

详细的还是看osak的代码吧，日文注释已经翻译成中文了：

/**
* 首先，只要在下一个相同数字到来之前没放这个球，下个数字来的时候直接将这个球放进去，和直接放是等效的。
* 为了简单，只在取出球的时候计算花费（取出最后该取出的球之后求和）、任意时刻箱子的状态转移是
* (1) 在时刻t将球放入，将原来的球取出，转移到t+1
* (2) 在时刻t不放入球，保持空的，转移到t+1
* (3) 在时刻t将球放入，保持该球，到下次相同编号到来的t'转移
* 这三种情况
* 另外，对于所有时刻，至少有一个箱子是“放入”的状态。
*
* 这种状态转移可以自然地用图描述：
* (1) v[t] -(1/w[v[t]])-> v[t+1]
* (2) v[t] -(∞/0)-> v[t+1]
* (3) v[t] -(1/0)-> v[t']
* 这里，由于(1)和(3)是一个连贯的动作，所以将(3)变形为
* (3') v[t] -(1/w[v[t]])-> v[t+1] -(1/-w[v[t]])-> v[t']
* 这样就合并了(1)和(3')，然后让所有(1)类型的边上面传输1单位流量即可。
*
* 变形后，最极端情况花费设为∑w[v[t]]的话
* (2) v[t] -(∞/0)-> v[t+1]
* (3'') v[t+1] -(1/-w[v[t]])-> v[t']
* 在上图跑F=M-1的最小费用流即可。
* 另外，当t+1 == t'的时候会产生负圈，此时得预先排除这样的顶点。
*
* 复杂度是O(K^2 + MNK)。
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;
const LL INF = 1LL << 59;

template<class Flow, class Cost>
struct Edge
{
	int from, to;
	Flow cap, flow;
	Cost cost;
	Edge *back;

	Edge(int from, int to, Flow cap, Cost cost, Edge *back)
		: from(from), to(to), cap(cap), flow(0), cost(cost), back(back)
	{}
};

template<class Flow, class Cost>
void add_edge(vector<vector<Edge<Flow, Cost> *>> &g, int src, int dst, Flow c, Cost d)
{
	Edge<Flow, Cost> *ea = new Edge<Flow, Cost>(src, dst, c, d, nullptr);
	Edge<Flow, Cost> *eb = new Edge<Flow, Cost>(dst, src, 0, -d, ea);
	ea->back = eb;
	g[src].push_back(ea);
	g[dst].push_back(eb);
}

template<class Flow, class Cost>
pair<Flow, Cost> primal_dual(vector<vector<Edge<Flow, Cost> *>> &g, int src, int sink, Flow max_flow)
{
	const int N = g.size();
	pair<Flow, Cost> res;
	vector<Cost> dist(N);
	vector<Edge<Flow, Cost> *> prev(N);
	for (Flow f = max_flow; f > 0;)
	{
		fill(dist.begin(), dist.end(), INF);
		fill(prev.begin(), prev.end(), nullptr);
		dist[src] = 0;

		while (true)
		{
			bool updated = false;
			for (int i = 0; i < N; ++i)
			{
				for (auto *e : g[i])
				{
					if (e->cap - e->flow > 0)
					{
						Cost nc = dist[e->from] + e->cost;
						if (nc < dist[e->to])
						{
							dist[e->to] = nc;
							prev[e->to] = e;
							updated = true;
						}
					}
				}
			}
			if (!updated)
				break;
		}
		if (prev[sink] == nullptr)
			break;

		Flow aug = f;
		for (auto *e = prev[sink]; e; e = prev[e->from])
		{
			aug = min(aug, e->cap - e->flow);
		}
		for (auto *e = prev[sink]; e; e = prev[e->from])
		{
			res.second += aug * e->cost;
			e->flow += aug;
			e->back->flow -= aug;
		}
		f -= aug;
		res.first += aug;
	}

	return res;
}

bool solve()
{
	int M, N, K;
	if (!(cin >> M >> N >> K))
		return false;

	vector<LL> ws(N);
	vector<int> as;	// 数字序列
	vector<vector<Edge<int, LL> *>> graph(K + 2);
	const int SRC = K;
	const int SINK = K + 1;
	for (int i = 0; i < N; ++i)
	{
		cin >> ws[i];
	}
	LL sum = 0;	// 总权重
	for (int i = 0; i < K; ++i)
	{
		int a;
		cin >> a;
		--a;
		if (as.size() > 0 && as.back() == a)
		{
			// do nothing 排除连续相同的序号
		}
		else
		{
			as.push_back(a);
			sum += ws[a];
		}
	}
	const int L = as.size();
	for (int i = 0; i < L; ++i)
	{
		// Edge to neighbor
		if (i + 1 < L)
		{
			add_edge(graph, i, i + 1, M, 0LL);	// v[t] -(∞/0)-> v[t+1]
		}
		// Edge to next same number
		auto it = find(as.begin() + i + 1, as.end(), as[i]);
		if (it != as.end())
		{
			add_edge(graph, i + 1, it - as.begin(), 1, -ws[as[i]]);	// v[t+1] -(1/-w[v[t]])-> v[t']
		}
	}
	add_edge(graph, SRC, 0, M, 0LL);
	add_edge(graph, L - 1, SINK, M, 0LL);
	auto res = primal_dual(graph, SRC, SINK, M - 1);
	cout << sum + res.second << endl;
	return true;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin.tie(0);
	ios::sync_with_stdio(0);

	while (solve());
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » AOJ 2266 Cache Strategy 题解 《挑战程序设计竞赛》