2016-06-15

『Noi2016十连测第一场 - 访问计划』

题目

问题描述

前不久，滋滋国来了一位白尛 FA 师，在滋滋国到处谈笑风生，滋滋国国王妹滋滋认为这个人姿势水平很高，便向他请教提高姿势水平的办法，白尛 FA 师说“滋滋国的哪一条路我没去过！”妹滋滋心想自己还没有好好考察过滋滋国的每一条道路呢，便计划进行一次访问来提高自己的姿势水平。

滋滋国有$N$个城市，编号从$0$到$N - 1$，其中$0$号城市是首都，这些城市被$N - 1$条道路连成一棵树，每个道路都有一个通过的花费，这个花费是每次通过时都需要付出的。

现在妹滋滋想要从首都出发，沿着道路行走，经过每条道路至少一次，并最终返回首都，除了沿着道路行走之外，妹滋滋还可以花费$C$元乘坐跳蚤巴士从一个城市直接跳到任意一个城市，然而因为各种奥妙重重的原因，妹滋滋最多只能搭乘$K$次跳蚤巴士。

现在妹滋滋找到了你，希望你为他安排一个最优的访问路径使得总花费最少，你只需要输出最小总花费即可。

输入格式

本题包含多组数据。

每组数据第一行三个整数$N, K, C$。

接下来$N - 1$行，每行三个整数$u, v, w$表示一条连接$u$和$v$的道路，通过这条道路的花费为$w$。

输出格式

对于每组数据输出一行一个整数表示最少的总花费。

样例输入1

点击这里下载

样例输出1

3
4

点击这里下载

样例输入2

点击这里下载

样例输出2

点击这里下载

数据范围与约定

对于$5\%$的数据：$K = 0$;$N \leq 200$;$\sum N \leq 2000$；

对于$10\%$的数据：$K = 1$;$N \leq 200$;$\sum N \leq 2000$；

对于$10\%$的数据：$K = 2$;$N \leq 200$;$\sum N \leq 2000$；

另有$20\%$的数据：$C = 1$;$K = N$；

另有$20\%$的数据：$0$号点度数至多为$2$，其他点度数至多为$3$；

对于$100\%$的数据：$N, K \leq 2000$;$\sum N \leq 10000$;$1 \leq C, u, v, w \leq 10000$。

题解

（稍后再补）

代码

#include <cstdio>
#include <cctype>
#include <vector>
using namespace std;
#define MAXN 2010
#define INF 1000000000
typedef pair<int, int> PII;
int readint()
{
	int x = 0, c;
	while (!isdigit(c = getchar()));
	do
		x = x * 10 + c - '0';
	while (isdigit(c = getchar()));
	return x;
}
int n, k, c;
vector<PII> edge[MAXN];
int fa[MAXN];
int sumson[MAXN];
bool vis[MAXN];
int ans[MAXN][MAXN];
int g[MAXN];
void dfs(int now)
{
	vis[now] = 1;
	ans[now][0] = 0;
	int sz = (int)edge[now].size();
	for (int i = 0; i < sz; i++)
	{
		int v = edge[now][i].first, l = edge[now][i].second;
		if (!vis[v])
		{
			fa[v] = now;
			dfs(v);
			for (int j = 0; j <= sumson[now] + sumson[v] && j <= 2 * k; j++)
				g[j] = INF;
			for (int j = 0; j <= sumson[now] && j <= 2 * k; j++)
				for (int t = 0; t <= sumson[v] && t <= 2 * k; t++)
					g[j + t] = min(g[j + t], ans[now][j] + ans[v][t] + l * (t % 2 ? 1 : 2));
			for (int j = 0; j <= sumson[now] + sumson[v] && j <= 2 * k; j++)
				ans[now][j] = g[j];
			sumson[now] += sumson[v];
		}
	}
	++sumson[now];
	ans[now][sumson[now]] = INF;
	for (int i = sumson[now]; i; i--)
		ans[now][i] = min(ans[now][i], ans[now][i - 1]);
}
int main()
{
	freopen("mzz.in", "r", stdin);
	freopen("mzz.out", "w", stdout);
	while (scanf("%d%d%d", &n, &k, &c) == 3)
	{
		for (int i = 0; i < n; i++)
		{
			edge[i].clear();
			fa[i] = 0;
			vis[i] = 0;
			sumson[i] = 0;
			for (int j = 0; j <= 2 * k; j++)
				ans[i][j] = INF;
		}
		int sum = 0;
		for (int i = 1; i < n; i++)
		{
			int u = readint();
			int v = readint();
			int w = readint();
			sum += w;
			edge[u].push_back(PII(v, w));
			edge[v].push_back(PII(u, w));
		}
		dfs(0);
		int a = INF;
		for (int i = 0; i <= k && i * 2 <= n; i++)
			a = min(a, ans[0][2 * i] + c * i);
		printf("%d\n", a);
	}
	return 0;
}