标签：根号分治，三元环
题目
题目传送门
Description
一个原力网络可以看成是一个可能存在重边但没有自环的无向图。每条边有一种属性和一个权值。属性可能是R、G、B三种当中的一种，代表这条边上原力的类型。权值是一个正整数，代表这条边上的原力强度。原力技术的核心在于将R、G、B三种不同的原力融合在一起产生单一的、便于利用的原力。为了评估一个能源网络，JYY需要找到所有满足要求的三元环（首尾相接的三条边），其中R、G、B三种边各一条。一个三元环产生的能量是其中三条边的权值之积。
现在对于给出的原力网络，JYY想知道这个网络的总能量是多少。网络的总能量是所有满足要求三元环的能量之和。
第一行包含两个正整数N、M。表示原力网络的总顶点个数和总边数。
接下来M行，每行包含三个正整数ui，vi，wi和一个字符ci。
表示编号ui和vi的顶点之间存在属性为ci权值为wi的一条边。
N≤50,000,M≤100,000,1≤Wi≤106
N
≤
50
,
000
,
M
≤
100
,
000
,
1
≤
W
i
≤
10
6
Output
输出一行一个整数，表示这个原力网络的总能量模10^9+7的值
4 6
1 2 2 R
2 4 3 G
4 3 5 R
3 1 7 G
1 4 11 B
2 3 13 B
Sample Output
828
分析
根号分治求三元环
本题的边数只有m，所以度数大于sqrt(m)的点最多只有sqrt(m)个，将其打上标记，作为大点处理
当三个都是大点的情况，暴力枚举三个点看是否符合情况，时间复杂度
O((m−−√)3)=O(mm−−√)
O
(
(
m
)
3
)
=
O
(
m
m
)
当三个点中存在小点的情况，枚举每个小点和其出边，判断这三个点是否有满足条件的三元环，保证枚举的点为三个点中最小的即可，时间复杂度同样
判断三元环是否满足条件，可以hash，也可以map
人懒写了个Map，卡常也没卡过去gg，所以我的代码并不能AC（貌似暴露了什么）
所以总的时间复杂度为
O(mm−−√)
O
(
m
m
)
（如果使用STL-Map那么多一个log的复杂度）
code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=
1,x=
0;
char ch=getchar();
while(ch<
'0'||ch>
'9'){
if(ch==
'-')f=-
1;ch=getchar();}
while(ch>=
'0'&&ch<=
'9'){x=x*
10+ch-
'0';ch=getchar();}
return x*f;
}
const int maxn=
5e4+
6,mod=
1e9+
7;
int last[maxn],n,m,blo,cnt,du[maxn],id[maxn];
char s[
3];ll ans;
struct edge{
int to,next,w,opt;}e[maxn<<
2];
struct node{
int x,y,z;
node(){}
node(
const int &a,
const int &b,
const int &c){x=a,y=b,z=c;}
inline bool operator < (
const node &a)
const{
return x==a.x?y==a.y?z<a.z:y<a.y:x<a.x;}
};
map<node,ll>Map;
void insert(
int u,
int v,
int w,
int opt){
e[++cnt]=(edge){v,last[u],w,opt};last[u]=cnt;du[u]++;
e[++cnt]=(edge){u,last[v],w,opt};last[v]=cnt;du[v]++;
}
int main()
{
n=read(),m=read(),blo=(
int)
sqrt(m);
rep(i,
1,m){
int u=read(),v=read(),w=read(),tmp;
scanf(
"%s",s);
if(s[
0]==
'R')tmp=
1;
if(s[
0]==
'G')tmp=
2;
if(s[
0]==
'B')tmp=
3;
insert(u,v,w,tmp);
Map[node(u,v,tmp)]=(Map[node(u,v,tmp)]+w)%mod;
Map[node(v,u,tmp)]=(Map[node(v,u,tmp)]+w)%mod;
}
rep(i,
1,n)
if(du[i]>=blo)id[++cnt]=i;
rep(i,
1,cnt)
rep(j,
1,cnt)
rep(k,
1,cnt)
ans=(ans+Map[node(id[i],id[j],
1)]*Map[node(id[i],id[k],
2)]%mod*Map[node(id[j],id[k],
3)])%mod;
rep(u,
1,n)
if(du[u]<blo)
reg(u)
if(du[e[i].to]>=blo||e[i].to>u)
for(
int j=e[i].next;j;j=e[j].next)
if(e[j].opt!=e[i].opt&&(du[e[j].to]>=blo||e[j].to>i))
ans=(ans+Map[node(e[i].to,e[j].to,
6-e[i].opt-e[j].opt)]*e[i].w%mod*e[j].w)%mod;
cout<<ans<<endl;
return 0;
}
