本题BZOJ权限题，但在bzojch上可以看题面。
题意：
N个点m条无向边，每个点有一个点权a。
对于任意一个三元环(i，j，k)（i<j<k），它的贡献为max(ai，aj，ak)
求所有三元环的贡献和。
N<100000，m<250000
Solution：
本题裸的三元环计数。
无向图三元环计数的问题大致做法：
统计每个点的度数，对于一条无向边$<u,v>$，若$deg[u]==deg[v]$则从编号小的点向编号大的点连有向边，否则从$deg$较大的向较小的点连有向边。
这样无向图就变为了一个DAG模型，然后扫一下每个点$u$，对其出点$v$打标记$vis[v]=u$，再对每个出点$v$的出点$w$判断是否满足$vis[w]=u$即可。
分析一波时间复杂度：
不难发现对于每条边$u\rightarrow v$，我们需要统计的是出度个数$out_v$，那么总的贡献是$\sum_\limits{i=1}^{i\leq n}{out_i}$。
假设$out_v\leq \sqrt m$，由于$u\rightarrow v$，则$deg_u\geq deg_v$，这样$u$最多$n$个，于是此时最坏复杂度为$O(n\sqrt m)$;
假设$out_v>\sqrt m$，由于$u\rightarrow v$，则$deg_u\geq deg_v$，于是$deg_u>\sqrt m$，这样$u$最多$\sqrt m$个，于是此时最坏时间复杂度$O(m\sqrt m)$。
综上所述，$n,m$同阶时，该算法时间复杂度$O(n\sqrt m)$。
那么本题三元环计数时累加答案就好了。
代码：
/*Code by 520 -- 9.10*/ #include<bits/stdc++.h> #define il inline #define ll long long #define RE register #define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++) #define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--) using namespace std; const int N=500005; int n,m,a[N],deg[N],vis[N]; int to[N],net[N],h[N],cnt; struct node{ int u,v; }e[N]; ll ans; int gi(){ int a=0;char x=getchar();bool f=0; while((x<‘0‘||x>‘9‘)&&x!=‘-‘)x=getchar(); if(x==‘-‘)x=getchar(),f=1; while(x>=‘0‘&&x<=‘9‘)a=(a<<3)+(a<<1)+(x^48),x=getchar(); return f?-a:a; } il void add(int u,int v){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt;} int main(){ n=gi(),m=gi(); For(i,1,n) a[i]=gi(); For(i,1,m) e[i].u=gi(),e[i].v=gi(),++deg[e[i].u],++deg[e[i].v]; For(i,1,m) { RE int u=e[i].u,v=e[i].v; if(deg[u]<deg[v]||deg[u]==deg[v]&&u>v) swap(u,v); add(u,v); } For(u,1,n){ for(RE int i=h[u];i;i=net[i]) vis[to[i]]=u; for(RE int i=h[u];i;i=net[i]) { RE int v=to[i]; for(RE int j=h[v];j;j=net[j]){ RE int w=to[j]; if(vis[w]==u)ans+=max(a[u],max(a[v],a[w])); } } } cout<<ans; return 0; }
原文：https://www.cnblogs.com/five20/p/9622701.html