BZOJ 5206 [Jsoi2017]原力
2018.05.28
题目大意
给你一个$n$个点$m$条边的无向图，边有边权和类型（三种），求所有三元环的边权乘积的和，三元环需要满足包含三种类型的边各一条。
这题炒鸡牛逼QwQ
这道题没啥思路……
有一个$O(n^3)$的做法，枚举三个点查询，所以找出所有度数大于$\sqrt{m}$的点，这些点的数目一定小于$\sqrt{n}$，之后对这些点$O(n^3)$查询，复杂度$O(n \sqrt{n})$
对于度数小于等于$\sqrt{m}$的点，暴力枚举它的所有度（两个），之后查询有没有第三条边。时间复杂度是$O(m \sqrt{m})$
#include <map>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long long ll;
#define mo 1000000007
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int ri()
{
int ret=0;char tmp=nc();
while(!isdigit(tmp)) tmp=nc();
while(isdigit(tmp)) ret=ret*10+(tmp-'0'),tmp=nc();
return ret;
}
inline int ric()
{
char ret=nc();
while(!isalpha(ret)) ret=nc();
if(ret=='R') return 1;
if(ret=='G') return 2;
if(ret=='B') return 3;
}
struct edge
{
int x,y,z;
edge(){}
edge(int _x,int _y,int _z){x=_x,y=_y,z=_z;}
bool operator<(const edge &tg)const
{
if(x==tg.x)
{
if(y==tg.y) return z<tg.z;
return y<tg.y;
}
return x<tg.x;
}
};
map<edge,ll>e;
int cnt[50010],point[50010],pts;
int to[200010],nxt[200010],val[200010],typ[200010],head[50010],tot;
ll ans;
inline void ae(int x,int y,int a,int b){to[++tot]=y,nxt[tot]=head[x],head[x]=tot,val[tot]=a,typ[tot]=b;}
int main()
{
int i,j,k,x,y,z,a,b;
int n=ri(),m=ri(),lim=sqrt(m);
for(i=1;i<=m;++i)
{
x=ri(),y=ri(),a=ri(),b=ric();
e[edge(x,y,b)]+=a,e[edge(y,x,b)]+=a;
ae(x,y,a,b),ae(y,x,a,b);
++cnt[x],++cnt[y];
}
for(i=1;i<=n;++i) if(cnt[i]>lim) point[++pts]=i;
for(i=1;i<=pts;++i)
for(j=i+1;j<=pts;++j)
for(k=j+1;k<=pts;++k)
{
x=point[i],y=point[j],z=point[k];
if(e.find(edge(x,y,1))!=e.end()&&e.find(edge(y,z,2))!=e.end()&&e.find(edge(z,x,3))!=e.end())
ans=(ans+1ll*e[edge(x,y,1)]%mo*e[edge(y,z,2)]%mo*e[edge(z,x,3)])%mo;
if(e.find(edge(x,y,1))!=e.end()&&e.find(edge(y,z,3))!=e.end()&&e.find(edge(z,x,2))!=e.end())
ans=(ans+1ll*e[edge(x,y,1)]%mo*e[edge(y,z,3)]%mo*e[edge(z,x,2)])%mo;
if(e.find(edge(x,y,2))!=e.end()&&e.find(edge(y,z,1))!=e.end()&&e.find(edge(z,x,3))!=e.end())
ans=(ans+1ll*e[edge(x,y,2)]%mo*e[edge(y,z,1)]%mo*e[edge(z,x,3)])%mo;
if(e.find(edge(x,y,2))!=e.end()&&e.find(edge(y,z,3))!=e.end()&&e.find(edge(z,x,1))!=e.end())
ans=(ans+1ll*e[edge(x,y,2)]%mo*e[edge(y,z,3)]%mo*e[edge(z,x,1)])%mo;
if(e.find(edge(x,y,3))!=e.end()&&e.find(edge(y,z,1))!=e.end()&&e.find(edge(z,x,2))!=e.end())
ans=(ans+1ll*e[edge(x,y,3)]%mo*e[edge(y,z,1)]%mo*e[edge(z,x,2)])%mo;
if(e.find(edge(x,y,3))!=e.end()&&e.find(edge(y,z,2))!=e.end()&&e.find(edge(z,x,1))!=e.end())
ans=(ans+1ll*e[edge(x,y,3)]%mo*e[edge(y,z,2)]%mo*e[edge(z,x,1)])%mo;
}
pts=0;
for(i=1;i<=n;++i) if(cnt[i]<=lim) point[++pts]=i;
for(i=1;i<=pts;++i)
{
x=point[i];
for(j=head[x];j;j=nxt[j])
{
y=to[j];
for(k=nxt[j];k;k=nxt[k])
{
z=to[k];
if(y<x&&cnt[y]<=lim) continue;
if(z<x&&cnt[z]<=lim) continue;
if(typ[j]==typ[k]) continue;
if(typ[j]!=1&&typ[k]!=1&&e.find(edge(y,z,1))!=e.end())
ans=(ans+1ll*val[j]*val[k]%mo*e[edge(y,z,1)])%mo;
if(typ[j]!=2&&typ[k]!=2&&e.find(edge(y,z,2))!=e.end())
ans=(ans+1ll*val[j]*val[k]%mo*e[edge(y,z,2)])%mo;
if(typ[j]!=3&&typ[k]!=3&&e.find(edge(y,z,3))!=e.end())
ans=(ans+1ll*val[j]*val[k]%mo*e[edge(y,z,3)])%mo;
}
}
}
printf("%lld\n",ans);
return 0;
}