[coci2015-2016 coii] torrent【树形dp 二分】

传送门：http://www.hsin.hr/coci/archive/2015_2016/

进去之后点最下面那个。

这道题没有想出来，可惜了，其实不难的。

题目是两个“源”的，我们先考虑单源的问题。先把这个源拉成树根，然后设f(i)为以结点i为树根的子树，全部收到文件所需要的时间，由于同一时间，结点i只能向其中一个子结点传送文件，那么假设son(i, j)表示结点i的第j个子结点（程序中不需要这个数组，这里只是为了叙述方便），那么f(i) = max{ j + f( son(i, j) )}。为了让这个max值最小，很显然需要把f( son(i, j) )按照从大到小排，即子树所需时间越长的，结点i就应该越早传文件给它。这样子就解决了单源的问题。

那么再考虑双源的。考虑从a到b的路径，若a到b的路径上，存在相邻的c，d两个点，很显然，在最佳方案里一定会有文件从a传到c，从b传到d，所以，如果把(c, d)这条边断开也不会影响到答案，这就变成了求两次单源的问题。因此，若把a到b的路径上的边按离a从远到近编号，设f_a(i)表示断开边i后，a所属的那棵树所需要的时间，设f_b(i)表示断开边i后，b所属的那棵树所需要的时间，那么最终答案ans = min{ max{f_a(i), f_b(i)} }。

这样会tle（我会说std有一个点，在我们学校的垃圾电脑上跑了92s吗？时限可是2s啊喂！你这标程怎么写的！），因此需要优化。很显然（又是显然），断开的边i离a越远，f_a(i)就会越大（其实也可以取等），f_b(i)就会越小（其实也可以取等），因此可以再二分一下断哪条边，就ok了！复杂度是O(n * (logn)^2)

p.s.主函数的前三行是开栈，以免递归爆栈。

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

const int maxn = 300005;

int n, a, b, t1, t2;

int head[maxn], to[maxn << 1], next[maxn << 1], lb, fa[maxn];

char mark[maxn];

std::vector<int> fson[maxn];

struct edge {

	int u, v;

} e[maxn];

int idx;

inline void ist(int aa, int ss) {

	to[lb] = ss;

	next[lb] = head[aa];

	head[aa] = lb;

	++lb;

}

void dfs(int r, int p) {

	fa[r] = p;

	for (int j = head[r]; j != -1; j = next[j]) {

		if (to[j] != p) {

			dfs(to[j], r);

		}

	}

}

int get_ans(int r, int p, int mar) {

	fson[r].clear();

	int son_num = 0, mx = 0;

	for (int j = head[r]; j != -1; j = next[j]) {

		if (to[j] != p && mark[to[j]] != -mar) {

			fson[r].push_back(get_ans(to[j], r, mar));

			++son_num;

		}

	}

	std::sort(fson[r].begin(), fson[r].end());

	for (std::vector<int>::iterator it = fson[r].begin(); it != fson[r].end(); ++it) {

		mx = std::max(mx, *it + son_num);

		--son_num;

	}

	return mx;

}

int main(void) {

	int size = 256 << 20; // 256MB

	char *p = (char*)malloc(size) + size;

	__asm__("movl %0, %%esp\n" :: "r"(p));

	freopen("torrent.in", "r", stdin);

	freopen("torrent.out", "w", stdout);

	memset(head, -1, sizeof head);

	memset(next, -1, sizeof next);

	scanf("%d%d%d", &n, &a, &b);

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

		scanf("%d%d", &t1, &t2);

		ist(t1, t2);

		ist(t2, t1);

	}

	dfs(a, 0);

	for (int i = b; i != a; i = fa[i]) {

		e[idx++] = (edge){fa[i], i};

	}

	int left = 0, right = idx - 1, mid;

	while (left < right) {

		mid = (left + right) >> 1;

		mark[e[mid].u] = -1;

		mark[e[mid].v] = 1;

		if (get_ans(a, 0, -1) > get_ans(b, 0, 1)) {

			left = mid + 1;

		}

		else {

			right = mid;

		}

		mark[e[mid].u] = mark[e[mid].v] = 0;

	}

	if (!left) {

		mark[e[0].u] = -1;

		mark[e[0].v] = 1;

		printf("%d\n", get_ans(b, 0, 1));

	}

	else {

		int ans1 = -666, ans2 = -666;

		mark[e[left].u] = -1;

		mark[e[left].v] = 1;

		ans1 = get_ans(b, 0, 1);

		mark[e[left].u] = mark[e[left].v] = 0;

		mark[e[left - 1].u] = -1;

		mark[e[left - 1].v] = 1;

		ans2 = get_ans(a, 0, -1);

		printf("%d\n", std::min(ans1, ans2));

	}

	return 0;

}

巴特西

[coci2015-2016 coii] torrent【树形dp 二分】

最新文章

热门文章