紫书习题 11-15 UVa 1668 （图论构造法）

参考了http://www.bubuko.com/infodetail-1276416.html

首先是逆向思维，向把每条边看作一条路径，然后再去合并

然后我们讨论怎么样合并时最优的

我们讨论当前的点u

那么首先直观感受，因为如果要合并一次，就需要两条边，

所以最多可以合并的不会超过度数（与其相连的边的总权值）的一半。

但这只是直观感受，并不是所有的情况都可以合并的了这么多。

当与当前点相连的边中有一条边的权值大于度数的一半的时候，不能合并

这么多。

比如说连了两条边，一条边权值为5，一条为7，那么显然只能合并5

次，而度数的一半是6.

再准确的一点来说，如果当前边的权值大于度数的一半，那么最优的做法

就是从这条边向其他所有的边合并，这样能合并的次数是最多的。

如果这条边以外的两条边合并了，只合并一次，还不如这条边和另外两条边

合并两次，合并次数更多，而且反正这条边到最后权值还是有剩的。

因为这条边和其他所有边合并，所以合并的次数就是剩下所有边的权值。

原理讲完了，看代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112345;

int degree[MAXN], maxw[MAXN], n;

int main()

{

	int T, kase = 0;

	scanf("%d", &T);

	while(T--)

	{

		memset(degree, 0, sizeof(degree));

		memset(maxw, 0, sizeof(maxw));

		int ans = 0;

		scanf("%d", &n);

		REP(i, 0, n - 1)

		{

			int u, v, w;

			scanf("%d%d%d", &u, &v, &w);

			u--; v--;

			degree[u] += w; degree[v] += w;

			maxw[u] = max(maxw[u], w);

			maxw[v] = max(maxw[v], w);

			ans += w;

		}

		REP(u, 0, n)

		{

			if((maxw[u] << 1) <= degree[u]) ans -= degree[u] >> 1;

			else ans -= degree[u] - maxw[u];

		}

		printf("Case #%d: %d\n", ++kase, ans);

	}

	return 0;

}

巴特西

紫书习题 11-15 UVa 1668 （图论构造法）

最新文章

热门文章

巴特西

紫书 习题 11-15 UVa 1668 （图论构造法）

最新文章

热门文章

紫书习题 11-15 UVa 1668 （图论构造法）