hdu4126.Genghis Khan the Conqueror

http://acm.hdu.edu.cn/showproblem.php?pid=4126

题意：给一个图（V<=3000) ，每次修改一条边的值（只增大），修改后求最小生成树，最后将所有生成树边的和加起来除以修改的次数。修改后边的值会复原。

思路：一个不知道怎么证的引用：新的生成树可以与原生成树相最多只有一条边的不同，而且不同的那条边就是被修改的边。那么每次修改后的询问就是去掉被修改的边，然后求出两个树最近的点。又有其中一棵子树一定包含他所有的子节点，那么就可以先用树dp求出一个点与一棵子树的最小距离，即求出dp[i][j] ，表示i点与j点以及j点子节点的最小距离。然后询问时，枚举不是包含所有子节点那棵树上的点，就可以直接知道这个点与另外一棵树最近的点的距离。最后取最小值，那么就完成一次询问。

总的来说，过程总结为：

A - 读入一个图，求出最小生成树；

B - 对生成树按前序重新编号；

C - 用树dp求出一个点与一棵树的最小距离；

D - 对每次询问，枚举一棵树的点，的出与另外一棵树的最小距离，在求最小值，注意不要把删除的那条边加进去。

虽然询问有10000次，但是最多只有3000条边要修改，所以复杂度O(N^2)

程序

// hdu4126.Genghis Khan the Conqueror - MST + treeDP
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define sqr(x) ((x) * (x))
#define two(x) (1 << (x))
#define X first
#define Y second

typedef long long LL;

const int MAXN = 3010;
const double eps = 1e-9;
const int INF = 1000000000;

int n, m, mark;
int cost[MAXN][MAXN], fa[MAXN], tof[MAXN], dfn[MAXN], sons[MAXN], mins[MAXN][MAXN], ans[MAXN], ndfn[MAXN];
bool flag[MAXN];

void init()
{
	memset(cost, -1, sizeof(cost));
	for (int i = 0; i < m; ++i)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		scanf("%d", &cost[x][y]);
		cost[y][x] = cost[x][y];
	}
	mark = 0;
}

void prim()
{
	memset(flag, 0, sizeof(flag));
	memset(tof, -1, sizeof(tof));
	fa[0] = -1;
	tof[0] = 0;
	bool mark = true;
	int x = 0;
	while (mark)
	{
		flag[x] = true;
		for (int i = 0; i < n; ++i) if (cost[x][i] >= 0 && !flag[i])
		{
			if (tof[i] < 0 || cost[x][i] < tof[i])
			{
				fa[i] = x;
				tof[i] = cost[x][i];
			}
		}
		mark = false;
		for (int i = 0; i < n; ++i) if (!flag[i] && tof[i] >= 0)
		{
			if (!mark || tof[i] < tof[x])
			{
				x = i;
				mark = true;
			}
		}
	}
}

void dfs(int x)
{
	sons[x] = 1;
	dfn[x] = mark;
	ndfn[mark++] = x;
	for (int i = 0; i < n; ++i) if (fa[i] == x)
	{
		dfs(i);
		sons[x] += sons[i];
	}
}

void work()
{
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			mins[dfn[i]][dfn[j]] = cost[i][j] >= 0? cost[i][j]: INF;
		}
	}
	for (int i = 0; i < n; ++i)
	{
		for (int j = n - 1; j > 0; --j)
		{
			mins[i][dfn[fa[ndfn[j]]]] = min(mins[i][j], mins[i][dfn[fa[ndfn[j]]]]);
		}
	}
}

void query()
{
	memset(ans, -1, sizeof(ans));
	int Q;
	double sum = 0;
	for (int i = 0; i < n; ++i) sum += tof[i];
	scanf("%d", &Q);
	for (int q = 0; q < Q; ++q)
	{
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		if (fa[x] != y && fa[y] != x) continue;
		if (fa[x] == y) swap(x, y);
		if (ans[y] == -1)
		{
			ans[y] = INF;
			for (int i = 0; i < n; ++i) if (x != i && (dfn[i] < dfn[y] || dfn[i] > dfn[y] + sons[y] - 1))
				ans[y] = min(ans[y], mins[dfn[i]][dfn[y]]);
			for (int i = 1; i < sons[y]; ++i)
				ans[y] = min(ans[y], mins[dfn[x]][dfn[y] + i]);
		}
		sum += (min(c, ans[y]) - tof[y]) * 1.0 / Q;
	}
	printf("%.4lf\n", sum);
}

int main()
{
	while (~scanf("%d%d", &n, &m) && n)
	{
		init();
		prim();
		dfs(0);
		work();
		query();
	}
    return 0;
}