Week6 作业 D - 数据中心 CCF-CSP 201812-4 C++实现

【知识背景】
在一个集中式网络中,存在一个根节点,需要长时间接收其余所有节点传输给它的反馈数据。
【题目描述】
存在一个 n节点的网络图,编号从1到n。该网络的传输是全双工的,所以是无
向图。如果两节点Vi, ls 相连,表明 Vi, s之间可以互相收发数据,边权是传输数据所需
时间 f。现在每个节点需要选择一条路径将数据发送到 root 号节点。希望求出一个最
优的树结构传输图,使得完成这个任务所需要的时间最少。root 节点只能接收数据,其
余任何一个节点可以将数据传输给另外的一个节点,但是不能将数据传输给多个节点。
所有节点可以接收多个不同节点的数据。

一个树结构传输图的传输时间为Tmax,其中 Tmax = max(Th),h为接收点在树中
的深度,T,= max(th), tnj 表示j条不同的边,这了条边接收点的深度都为 h。
【输入格式】
从标准输入读入数据。
输入的第1行包含一个正整数 n,保证 ns5x 10。
输入的第2行包含一个正整数 m,保证 ms 10%。
输入的第3行包含一个正整数 roo1,保证 root s 5x 104。

样例输入
4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2
样例输出
4
样例说明
　　下图是样例说明。

【子任务】
子任务1(20分):ns 10?,
子任务2(30 分):ns 103, ms3x104。
子任务3(20 分):ns 104, ms5x 104。
F1E:3 4 (30 ): n< 5× 105, m< 105.
PTATE%: vi, U;, t;, Ril v; < 5 × 104, u; < 5 × 104, t; < 10°, u; # V;
m< 4, 500.

解题思路

kruskal最小生成树，输出在生成树过程中选择的最大的边。
正在写。。。

程序源码

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;


struct node {
	int a;
	int b;
	int l;
	int m;
	node* next;
	node(int aa,int bb, int ll, node* nnext) :a(aa),b(bb), l(ll), next(nnext) {
		m=-1;
	}
	node(node* nnext) :next(nnext) {}
};

node** L;
int* touch;
int* result;
int* point;
int end=0;

int dfs(node* currentnode, const int & flag,int level) {
	int themax=0,current;
	node* thisnode = currentnode;
	while (thisnode != NULL) {
		if (touch[thisnode->b] != flag) {
			touch[thisnode->b] = flag;
			if(thisnode->m==-1){
				current=dfs(L[thisnode->b], flag, level+1)+thisnode->l; ///
				thisnode->m=current;
			}
			else{
				current=thisnode->m;
			}
			
			if(current>themax){
				themax=current;
			}
		}
		thisnode = thisnode->next;
	}
	if(result[currentnode->a]<themax){
		result[currentnode->a]=themax;
	//	cout<<level<<"-";
	}
	return themax;
	
	
}



int main() {
	int n, a, b;
	while (scanf("%d", &n) != EOF) {

		L=new node* [10001]{ NULL };

		touch=new int [10001]{ 0 };
		result=new int [10001]{ 0 };
		point=new int [10001]{ 0 };

		for (int i = 2; i <= n; i++) {
			scanf("%d%d", &a, &b);

			L[i] = new node(i, a, b, L[i]);
			L[a] = new node(a, i, b, L[a]);

			touch[i]++;
			touch[a]++;
		}

		if (n < 2) {
			cout << 0 << endl;
			continue;
		} //wancheng shuju shuru 


		int totalPoint = 0;
		// zhaodao chudian wei 1 de dian, baocun 
		for (int i = 1; i <= n; i++) {
			if (touch[i] == 1) {
				point[totalPoint] = i;
				totalPoint++;
			}
		}
		
		for (int i = 0; i < totalPoint; i++) {
			touch[point[i]] = i - totalPoint - 5;
		//	cout<<i<<"st time:\n";
			dfs(L[point[i]], i - totalPoint - 5,0);
		//	cout<<"\n";
		
		}

		for (int i = 1; i <= n; i++) {
			printf("%d\n", result[i]);
		}

		delete[] L;

		delete[] touch;
		delete[] result;
		delete[] point;

	}
	return 0;
	
}