题目大意

给你一个$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;
}