Bzoj5206 [jsoi2017]原力

根号分治求三元环

Posted by yjjr's blog on March 15, 2018

标签:根号分治,三元环

题目

题目传送门

Description

一个原力网络可以看成是一个可能存在重边但没有自环的无向图。每条边有一种属性和一个权值。属性可能是R、G、B三种当中的一种,代表这条边上原力的类型。权值是一个正整数,代表这条边上的原力强度。原力技术的核心在于将R、G、B三种不同的原力融合在一起产生单一的、便于利用的原力。为了评估一个能源网络,JYY需要找到所有满足要求的三元环(首尾相接的三条边),其中R、G、B三种边各一条。一个三元环产生的能量是其中三条边的权值之积。

现在对于给出的原力网络,JYY想知道这个网络的总能量是多少。网络的总能量是所有满足要求三元环的能量之和。

Input

第一行包含两个正整数N、M。表示原力网络的总顶点个数和总边数。

接下来M行,每行包含三个正整数ui,vi,wi和一个字符ci。

表示编号ui和vi的顶点之间存在属性为ci权值为wi的一条边。

Output

输出一行一个整数,表示这个原力网络的总能量模10^9+7的值

Sample Input

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)个,将其打上标记,作为大点处理

  • 当三个都是大点的情况,暴力枚举三个点看是否符合情况,时间复杂度

  • 当三个点中存在小点的情况,枚举每个小点和其出边,判断这三个点是否有满足条件的三元环,保证枚举的点为三个点中最小的即可,时间复杂度同样


判断三元环是否满足条件,可以hash,也可以map

人懒写了个Map,卡常也没卡过去gg,所以我的代码并不能AC(貌似暴露了什么)

所以总的时间复杂度为(如果使用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;
}
//**********head by yjjr**********
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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr