洛谷:P1351
OJ:I1351
暴力算法: 70分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | /**************************************************************** * Description: 2014年提高组第二题 联合权值 70分 * Author: Alex Li * Date: 2024-10-11 17:18:25 * LastEditTime: 2024-10-11 18:26:09 ****************************************************************/ #include <iostream> #include <vector> #include <algorithm> using namespace std; const int MOD = 10007; int main() { //ios::sync_with_stdio(false); //cin.tie(0); int n; cin >> n; vector<vector<int>> adj(n + 1); // 邻接表,节点编号从1开始 vector<int> W(n + 1); // 节点权值,节点编号从1开始 // 读入边,构建邻接表 for (int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } // 读入节点权值 for (int i = 1; i <= n; ++i) { cin >> W[i]; } int max_joint_weight = 0; // 最大联合权值 int total_sum = 0; // 所有联合权值之和 // 遍历每一条边 for (int u = 1; u <= n; ++u) { for (int v : adj[u]) { if (u < v) { // 为了避免重复计算,每条边只处理一次(u < v) // 处理与边(u,v)相关的节点对 // 遍历v的邻居,排除u for (int w : adj[v]) { if (w != u) { int joint_weight = W[u] * W[w]; total_sum = (total_sum + joint_weight) % MOD; if (joint_weight > max_joint_weight) { max_joint_weight = joint_weight; } } } // 遍历u的邻居,排除v for (int w : adj[u]) { if (w != v) { int joint_weight = W[v] * W[w]; total_sum = (total_sum + joint_weight) % MOD; if (joint_weight > max_joint_weight) { max_joint_weight = joint_weight; } } } } } } cout << max_joint_weight << " " << total_sum << endl; return 0; } |
DP算法: 100分
addEdge
函数实现图的邻接表构建,每条边存储为两个方向(无向边),并将邻接点的权值存储起来。processNode
函数:通过遍历每个节点的邻居节点,计算所有与该节点相连的邻居的联合权值,并动态维护邻居节点中的最大值和次大值,以此来计算最大联合权值。max1
和max2
,在每次遍历中实时更新。代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | /**************************************************************** * Description: 2014年提高组第二题 联合权值 100分 * Author: Alex Li * Date: 2024-10-11 18:00:52 * LastEditTime: 2024-10-11 18:05:29 ****************************************************************/ #include <iostream> using namespace std; const int N = 2e5 + 5, MOD = 10007; // 边结构体,表示从一个点到另一个点的连接关系 struct Edge { int to, next; } edges[N * 2]; int head[N], edgeCount, values[N]; // head: 邻接表头节点索引, edgeCount: 边计数, values: 各点的权值 int n, totalWeightSum, x, y, maxPairWeight; // 初始化邻接表,将边加入邻接表中 void addEdge(int u, int v) { edges[++edgeCount].to = v; edges[edgeCount].next = head[u]; head[u] = edgeCount; } // 计算以某个节点为中转点的联合权值 void processNode(int u) { int sumOfNeighbors = 0; // 记录邻居点的权值和 int max1 = 0, max2 = 0; // 记录邻居节点中最大的两个权值 // 遍历当前节点 u 的所有邻居 for (int k = head[u]; k; k = edges[k].next) { int neighborValue = values[edges[k].to]; // 获取邻居节点的权值 // 动态更新两个最大的权值 if (neighborValue > max1) { max2 = max1; max1 = neighborValue; } else if (neighborValue > max2) { max2 = neighborValue; } // 更新总的联合权值之和 totalWeightSum = (totalWeightSum + sumOfNeighbors * neighborValue) % MOD; // 累加当前邻居的权值 sumOfNeighbors = (sumOfNeighbors + neighborValue) % MOD; } // 更新最大联合权值,max1 和 max2 分别为当前节点邻居中最大的两个权值 maxPairWeight = max(maxPairWeight, max1 * max2); } int main() { // 输入节点数 cin >> n; // 输入边信息,建立无向图 for (int i = 1; i < n; i++) { cin >> x >> y; addEdge(x, y); addEdge(y, x); } // 输入每个节点的权值 for (int i = 1; i <= n; i++) { cin >> values[i]; } // 枚举每个节点作为中转点,计算联合权值 for (int i = 1; i <= n; i++) { processNode(i); } // 输出结果,最大联合权值和联合权值之和(后者需要乘以2并取模) cout << maxPairWeight << " " << (totalWeightSum * 2) % MOD << endl; return 0; } |