Codeforces 398C Tree and Array(构造)

题目链接：Codeforces 398C Tree and Array

题目大意：给出n，表示有n个节点，每个节点有个值记录在t[i]中，初始为0，现在要求构造出一棵无向的树，既有n-1条边，保证所有点联通，现在每增加一条边u，v，x（假设u<v）那么t[i]就要增加x（u≤i≤v),现在要求在构造出的树中可以选出不少于n/2对点（u，v）保证∑（u≤i≤v）t[i] = dis（dis为从点u到v的路径上所有边的权值和）

解题思路：t = n/2，将t+1到n逐个相连成一条，然后i和t+i相连（1≤i≤t),这样的话为了使得i和i+1满足，只需要修改t+i和t+i+1这条边的权值即可；如果是奇数的话可以将n点直接舍弃在最后；但是这样只构造出n/2-1条边，这时可以控制一下各个1到3这条路径；n为5的话可以特判一下，因为奇数时我是将n这个点舍弃。

#include <stdio.h>
#include <string.h>

int main () {
	int n;
	scanf("%d", &n);
	if (n == 5) {
		printf("1 2 3\n1 3 3\n2 4 2\n4 5 1\n");
		printf("3 4\n3 5\n");
	} else {
		int t = n/2;
		for (int i = 1; i <= t; i++) printf("%d %d %d\n", i, i + t, 1);
		for (int i = 1; i+t < n; i++) printf("%d %d %d\n", i+t, i+t+1, 2*i-1);
		for (int i = 1; i < t; i++) printf("%d %d\n", i, i+1);
		printf("1 3\n");
	}

	return 0;
}

Codeforces 398C Tree and Array(构造),布布扣,bubuko.com

Codeforces 398C Tree and Array(构造)

原文：http://blog.csdn.net/keshuai19940722/article/details/20624419