下面是 LCP 16. 游乐园的游览计划 的 C 语言实现。解题思路这道题的核心是在图中找出两个三角形它们至少共享一个顶点使得所有不同顶点的权值和最大。步骤一三元环计数找所有三角形点数和边数都是 10^4 级别直接暴力 O(N^3) 不可行。采用定向 枚举的经典方法1. 按度数排序度数大的排前面度数相同则编号大的排前面。2. 定向建图对于每条边 (u,v)让排序更靠前rank 更小的点指向更靠后的点。这样每个三角形只会被找到一次。3. 枚举三角形遍历每个点 i标记其所有出边邻居再枚举邻居 v 的出边邻居 w若 w 也被标记则 (i,v,w) 构成一个三角形。时间复杂度为 O(M\sqrt{M})。步骤二三角形拼接对于每个顶点 v收集所有包含它的三角形按权值和从大到小排序。关键观察如果最优解的两个三角形都包含顶点 v那么将包含 v 的三角形按权值和排序后最优解中至少有一个三角形在前 3 名之内贪心 / 鸽笼原理。因此对每个顶点 v只需取权值和最大的前 3 个三角形分别与所有包含 v 的三角形组合计算并集的最大权值和即可。步骤三计算两个三角形的并集权值和两个三角形最多 6 个点重复的点只算一次。直接暴力判断 9 种重复情况并减去重复权值。---C 语言代码c#include stdlib.h#include string.h#define MAXN 10005static int val[MAXN];static int deg[MAXN];static int id[MAXN];static int rnk[MAXN];static int vis[MAXN];static int edge_u[MAXN];static int edge_v[MAXN];/* 三角形结构 */typedef struct {int a, b, c;} Tri;/* 按度数从大到小排序度数相同则编号大的排前面 */static int cmp_deg(const void *a, const void *b) {int x *(const int *)a;int y *(const int *)b;if (deg[x] ! deg[y]) return deg[y] - deg[x];return y - x;}/* 按三角形权值和从大到小排序 */static int cmp_tri(const void *a, const void *b) {const Tri *t1 (const Tri *)a;const Tri *t2 (const Tri *)b;int s1 val[t1-a] val[t1-b] val[t1-c];int s2 val[t2-a] val[t2-b] val[t2-c];return s2 - s1;}/* 计算两个三角形的并集权值和去重 */static int calc_tri(const Tri *a, const Tri *b) {int res val[a-a] val[a-b] val[a-c] val[b-a] val[b-b] val[b-c];if (a-a b-a) res - val[b-a];if (a-b b-a) res - val[b-a];if (a-c b-a) res - val[b-a];if (a-a b-b) res - val[b-b];if (a-b b-b) res - val[b-b];if (a-c b-b) res - val[b-b];if (a-a b-c) res - val[b-c];if (a-b b-c) res - val[b-c];if (a-c b-c) res - val[b-c];return res;}int maxWeight(int **edges, int edgesSize, int *edgesColSize,int *value, int valueSize) {int n valueSize;int m edgesSize;for (int i 0; i n; i) {val[i] value[i];deg[i] 0;id[i] i;}for (int i 0; i m; i) {int u edges[i][0];int v edges[i][1];edge_u[i] u;edge_v[i] v;deg[u];deg[v];}/* 按度数排序确定每个点的 rank */qsort(id, n, sizeof(int), cmp_deg);for (int i 0; i n; i) {rnk[id[i]] i;}/* ---------- 定向建图度数大的指向度数小的 ---------- */int *adj_sz calloc(n, sizeof(int));for (int i 0; i m; i) {int u edge_u[i];int v edge_v[i];if (rnk[u] rnk[v]) {int t u; u v; v t;}adj_sz[u];}int **adj malloc(n * sizeof(int *));for (int i 0; i n; i) {adj[i] malloc(adj_sz[i] * sizeof(int));adj_sz[i] 0;}for (int i 0; i m; i) {int u edge_u[i];int v edge_v[i];if (rnk[u] rnk[v]) {int t u; u v; v t;}adj[u][adj_sz[u]] v;}/* ---------- 找所有三角形 ---------- */Tri **tris calloc(n, sizeof(Tri *));int *tri_sz calloc(n, sizeof(int));int *tri_cap calloc(n, sizeof(int));for (int i 0; i n; i) {for (int j 0; j adj_sz[i]; j) {vis[adj[i][j]] 1;}for (int j 0; j adj_sz[i]; j) {int v adj[i][j];for (int k 0; k adj_sz[v]; k) {int w adj[v][k];if (vis[w]) {Tri t {i, v, w};/* 将三角形加入 i, v, w 三个顶点的列表 */for (int idx 0; idx 3; idx) {int node (idx 0) ? i : (idx 1) ? v : w;if (tri_sz[node] tri_cap[node]) {tri_cap[node] tri_cap[node] ? tri_cap[node] * 2 : 4;tris[node] realloc(tris[node],tri_cap[node] * sizeof(Tri));}tris[node][tri_sz[node]] t;}}}}for (int j 0; j adj_sz[i]; j) {vis[adj[i][j]] 0;}}/* ---------- 枚举拼接取最大权值和 ---------- */int ans 0;for (int i 0; i n; i) {if (tri_sz[i] 0) continue;qsort(tris[i], tri_sz[i], sizeof(Tri), cmp_tri);int limit tri_sz[i] 3 ? tri_sz[i] : 3;for (int t 0; t limit; t) {for (int k 0; k tri_sz[i]; k) {int res calc_tri(tris[i][t], tris[i][k]);if (res ans) ans res;}}}/* ---------- 释放内存 ---------- */for (int i 0; i n; i) {free(adj[i]);free(tris[i]);}free(adj);free(adj_sz);free(tris);free(tri_sz);free(tri_cap);return ans;}---复杂度分析项目 复杂度时间 O(M\sqrt{M})主要来自三元环计数和排序拼接空间 O(M\sqrt{M})存储所有三角形最坏情况其中 N \le 10^4,\ M \le 10^4该算法可以高效通过。