数据中心

问题描述

在一个集中式网络中，存在一个根节点，需要长时间接收其余结点传输给它的反馈数据。
存在一个 n 结点的网络图，编号从 1 到 n。该网络的传输时全双工的，所以是无向图。如果两结点 vi, ui 相连，表明 vi, ui 之间可以互相收发数据，边权是传输数据所需时间 ti。现在每个结点需要选择一条路径将数据发送到 root 号节点。希望求出一个最优的树结构传输图，使得完成这个任务所需要的时间最少。root 结点只能接收数据，其余任何一个节点可以将数据传输给另外的一个节点，但是不能将数据传输给多个节点。所有节点可以接收多个不同节点的数据。
一个树结构传输图的传输时间为Tmax，其中Tmax = max(Th), h为接收点在树中的深度，Th = max(th,j), th,j表示 j 条不同的边，这 j 条边接收点的深度都为 h。

Input

从标准输入读入数据。
输入的第 1 行包含一个正整数 n，保证 n ≤ 5 × 10^4
输入的第 2 行包含一个正整数 m，保证 m ≤ 10^5。
输入的第 3 行包含一个正整数 root，保证 root ≤ 5 × 10^4
输入的第 4 行至第 3+m 行包含 3 个正整数 vi, ui, ti，保证 vi ≤ 5 × 10^4, ui ≤ 5 × 10^4, ti ≤ 10^6, vi ≠ ui。

Output

输出到标准输出。
输出仅有一行，包含一个正整数 ans，表示最优的树结构流水线所耗时 Tmax。

Sample

Input: 
4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2

Output: 
4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2

Note

Limitation

Time limit		1000 ms
Memory limit	524288 kB

解题思路

本题又臭又长，题设变量花里胡哨，样例解释东拉西扯，题意大致就是n个节点的带权无向图，连接每个点求总权重最小，其实就是一个最小生成树问题，可以用Kruskal算法，算法具体思路同上一篇。

就是吐槽一下test好像跑了120组，测试用了7分钟……也太多了吧，在那等着出结果等的心好慌，测那么多万一WA了还是啥的会崩溃的……🙃

源代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxN = 305;

struct edge {
	int u, v, w;
	edge(int _u, int _v, int _w) :u(_u), v(_v), w(_w) {  }
};

bool cmp(edge a, edge b) {
	return a.w < b.w;
}

int par[maxN];

int find(int x) {
	if (par[x] == x)
		return x;
	return par[x] = find(par[x]);
}

int kruskal(int n, vector<edge> v) {
	int ans = 0;
	int edgeCount = 0;
	for (int i = 0; i <= n; i++)
		par[i] = i;
	sort(v.begin(), v.end(), cmp);

	for (int i = 0; i != v.size(); i++) {
		int p1 = find(v[i].u);
		int p2 = find(v[i].v);
		if (p1 != p2) {
			par[p1] = p2;
			ans += v[i].w;
			edgeCount++;
			if (edgeCount == n)
				break;
		}
	}

	return ans;
}

int main() {
	int n;
	cin >> n;
	vector<edge> v;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		edge e1(0, i, a);
		edge e2(i, 0, a);
		v.push_back(e1);
		v.push_back(e2);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int a;
			cin >> a;
			if (a != 0) {
				edge e(i, j, a);
				v.push_back(e);
			}
		}
	}
	int res = kruskal(n, v);
	cout << res << endl;
	return 0;
}