竞赛讨论区 > 三元环学习笔记
头像
xuxuxuxuxu
发布于 2019-04-27 10:21
+ 关注

三元环学习笔记

三元环是什么？

三元环是

求无向图的三元环有两种方法：

做法1：

①统计每个点的度数 

②入度$sqrt(m)$的分为第二类

 ③对于第一类，暴力每个点，然后暴力这个点的任意两条边，再判断这两条边的另一个端点是否连接

因为m条边最多每条边遍历一次，然后暴力的点的入度，所以复杂度约为O(msqrt(m))

 ④对于第二类，直接暴力任意三个点，判断这三个点是否构成环，因为这一类点的个数不会超过$sqrt(m)个，所以复杂度约为$$O(sqrt(m)^3)=O(msqrt(m))$

⑤判断两个点是否连接可以用set，map和Hash都行,根据具体情况而行

这种做法建的是双向边，常数很大 

#include
using namespace std;
const int N=1e6+5;
int n,m,x,y,z,ans,du[N],vis[N];
vectora,b,g[N];
mapmp[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
        du[x]++;
        du[y]++;
        mp[x][y]=1;
        mp[y][x]=1;
    }
    for(int i=1;i<=n;i++)
        if(du[i]<=sqrt(m))a.push_back(i);
        else b.push_back(i);
    for(int i=0;i<a.size();i++)
    {
        x=a[i];
        vis[x]=true;
        for(int j=0;j<g[x].size();j++)
        {
            y=g[x][j];
            if(vis[j])continue;
            for(int k=j+1;k<g[x].size();k++)
            {
                z=g[x][k];
                if(!vis[z]&&mp[y].count(z))ans++;
            }
        }
    }
    for(int i=0;i<b.size();i++)
    {
        for(int j=i+1;j<b.size();j++)
        {
            x=b[i];y=b[j];
            if(mp[x].count(y)==0)continue;
            for(int k=j+1;k<b.size();k++)
            {
                z=b[k];
                if(mp[x].count(z)&&mp[y].count(z))ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

更优的做法2:

建有向边 复杂度为$O(msqrt(n))$

对所有边按照两端点的度数定向，度数小的往度数大的走，度数相同则按编号(值)小到大走，这样定向后

可以保证是个有向无环图。

为什么呢，要想定向存在环，则这个环上的点度数必须相同，由于保证了编号从小到大走,所以是不可能存在

环的。

这样定向同时还保证了每个点的出度不超过$sqrt(n)$，乍一眼看觉得应该是$sqrt(m)$的，仔细一想确实比这个

低，不过不知道怎么证。

#include
#define P pair
using namespace std;
const int N=5e5+5;
vector >G[N];
int n,m,Sz,u,v,X[N],Y[N],pos[N],vis[N],du[N];
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        Sz=sqrt(m);
        for(int i=1;i<=n;i++)
        {
            vis[i]=du[i]=pos[i]=0;
            G[i].clear();
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&X[i],&Y[i]);
            du[X[i]]++;
            du[Y[i]]++;
        }
        for(int i=0;i<m;i++)
        {
            if(du[X[i]]<du[Y[i]])G[X[i]].push_back(make_pair(Y[i],i));
            else if(du[Y[i]]<du[X[i]])G[Y[i]].push_back(P(X[i],i));
            else{
                if(X[i]<Y[i])G[X[i]].push_back(P(Y[i],i));
                else G[Y[i]].push_back(P(X[i],i));
            }
        }
        long long ans=0;
        for(int i=0;i<m;i++)
        {
            u=X[i];v=Y[i];
            for(int j=0;j<G[u].size();j++)
            {
                P xu=G[u][j];
                int jia=xu.first;
                pos[jia]=xu.second;
                vis[jia]=i+1;
            }
            for(int j=0;j<G[v].size();j++)
            {
                P xu=G[v][j];
                int jia=xu.first;
                if(vis[jia]==i+1)ans++;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

题目： Counting Stars

给一张n个点m条边的无向图，问有多少个

其中满足 &&

显然是由两个有公共边的三元环构成的

题解：

我们记录一下每条边能构成的三元环数， 为第i条边的三元环数

我们用做法二做这题：

#include
#define P pair
using namespace std;
const int N=5e5+5;
vector >G[N];
int n,m,Sz,u,v,X[N],Y[N],cnt[N],pos[N],vi[N],du[N];
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        Sz=sqrt(m);
        for(int i=1;i<=n;i++)
        {
            vi[i]=du[i]=pos[i]=0;
            G[i].clear();
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&X[i],&Y[i]);
            du[X[i]]++;
            du[Y[i]]++;
        }
        for(int i=0;i<m;i++)
        {
            cnt[i]=0;
            if(du[X[i]]<du[Y[i]])G[X[i]].push_back(make_pair(Y[i],i));
            else if(du[Y[i]]<du[X[i]])G[Y[i]].push_back(P(X[i],i));
            else{
                if(X[i]<Y[i])G[X[i]].push_back(P(Y[i],i));
                else G[Y[i]].push_back(P(X[i],i));
            }
        }
        long long ans=0;
        for(int i=0;i<m;i++)
        {
            u=X[i];v=Y[i];
            for(int j=0;j<G[u].size();j++)
            {
                P vp=G[u][j];
                pos[vp.first]=vp.second;
                vi[vp.first]=i+1;
            }
            for(int j=0;j<G[v].size();j++)
            {
                P vp=G[v][j];
                int vv=vp.first;
                if(vi[vv]==i+1)
                {
                    cnt[i]++;
                    cnt[pos[vv]]++;
                    cnt[vp.second]++;
                }
            }
        }
        for(int i=0;i<m;i++)ans+=1ll*cnt[i]*(cnt[i]-1)/2;
        printf("%lld\n",ans);
    }
    return 0;
}

题目: 3498: PA2009 Cakes

N个点m条边，每个点有一个点权a。

对于任意一个三元环(j，j，k)（i<j<k），它的贡献 为max(ai，aj，ak)

求所有三元环的贡献和。

N<100000，，m<250000。

题解：

按照值从大到小排序，用做法二找到环就把加上点i的值

#include
using namespace std;
const int N=1e6+5;
int n,m,rank[N],du[N],vis[N];
struct node{
    int val,id;
}a[N];
vectorg[N];
mapmp[N];
char buf[1<<21],*p1=buf,*p2=buf;
inline int gc()
{
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int ret=0,f=0;
    char c=gc();
    while(!isdigit(c))
    {
        if(c=='-')f=1;
        c=gc();
    }
    while(isdigit(c))
    {
        ret=ret*10+c-48;
        c=gc();
    }
    if(f)return -ret;
    return ret;
}
bool cmp(node a,node b)
{
    return a.val>b.val;
}
int main()
{
    freopen("xjh.in","r",stdin);
    freopen("xjh.out","w",stdout);
    n=read();m=read();
    int size=sqrt(m);
    for(int i=1;i<=n;i++)
    {
        a[i].val=read();
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)rank[a[i].id]=i;
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        if(rank[x]<rank[y])
        {
            g[x].push_back(y);
            mp[x][y]=1;
            du[x]++;
        }
        else{
            g[y].push_back(x);
            mp[y][x]=1;
            du[y]++;
        }
    }
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        int x=a[i].id;
        for(int j=0;j<g[x].size();j++)
            vis[g[x][j]]=x;
        for(int j=0;j<g[x].size();j++)
        {
            int y=g[x][j];
            if(du[y]<=size)
            {
                for(int k=0;k<g[y].size();k++)
                {
                    int z=g[y][k];
                    if(vis[z]==x)ans+=a[i].val;
                }
            }
            else{
                for(int k=0;k<g[x].size();k++)
                {
                    int z=g[x][k];
                    if(mp[y].count(z))ans+=a[i].val;
                }
            }
        }
    }
    cout<<ans;
}

题目:5407: girls

有一个图，你要选定三个点，保证三个点之间两两无互相连边，当点的时候，你获得的收益为，求所有符合情况的收益和。

题解：

可以用容斥原理，即所有的情况−至少有一对有连边+至少有两对有连边−三对都有连边 。

1. 对于所有的情况，可以考虑每个点来算贡献
2. 对于至少有一对连边的情况，可以枚举一个点和它的连边，然后用前缀和计算处余下来的所有的点。
3. 对于至少有两对连边的情况，可以枚举中间那个于两个点都有连边的点，然后对于它连接的每一个点计算贡献
4. 对于至少有三对连边的情况，可以三元环怒搞

#include
using namespace std;
#define ll long long
const int N=1e6+5;
int n,m;
unsigned long long A,B,C,x,y,z,ans,xu[N],du[N],suma[N],sumb[N],sumc[N];
bool vis[N];
vectora,b,g[N];
mapmp[N];
signed main()
{
    scanf("%d%d",&n,&m);
    cin>>A>>B>>C;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x++;y++;
        du[x]++;du[y]++;
        g[x].push_back(y);
        g[y].push_back(x);
        mp[x][y]=1;
        mp[y][x]=1;
    }
    for(int i=1;i<=n;i++)sort(g[i].begin(),g[i].end());
    for(int i=1;i<=n;i++)
    {
        ans+=A*(i-1)*((ll)(n-i-1)*(n-i)/2);
        ans+=B*(i-1)*(i-1)*(n-i);
        ans+=C*(i-1)*((ll)(i-1)*(i-2)/2);
    }
    for(int i=1;i<=n;i++)
    {
        suma[i]=suma[i-1]+(i-1)*A;
        sumb[i]=sumb[i-1]+(i-1)*B;
        sumc[i]=sumc[i-1]+(i-1)*C;
    }
    for(int i=1;i<=n;i++)
    {
        int siz=g[i].size()-1;
        unsigned long long cnt0=0,cnt1=0;
        for(int j=0;j<=siz;j++)
        {
            int v=g[i][j];
            if(v<i)
            {
                cnt0++;
                ans-=suma[v-1]+B*(v-1)*(v-1)+C*(i-1)*(v-1);
                ans+=A*(v-1)*(siz-j)+B*(v-1)*j;
            }
            else{
                cnt1++;
                ans-=A*(i-1)*(n-v)+B*(v-1)*(n-v)+sumc[n]-sumc[v];
                ans-=A*(i-1)*(v-i-1)+sumb[v-1]-sumb[i]+C*(v-1)*(v-i-1);
                ans+=C*(v-1)*j+B*(v-1)*(siz-j);
            }
        }
        ans+=A*(i-1)*(cnt1*(cnt1-1)/2)+B*(i-1)*cnt0*cnt1+C*(i-1)*cnt0*(cnt0-1)/2;
    }
    int size=sqrt(m);
    for(int i=1;i<=n;i++)
        if(du[i]<=size)a.push_back(i);
        else b.push_back(i);
    for(int i=0;i<a.size();i++)
    {
        x=a[i];
        vis[x]=true;
        for(int j=0;j<g[x].size();j++)
        {
            y=g[x][j];
            if(vis[j])continue;
            for(int k=j+1;k<g[x].size();k++)
            {
                z=g[x][k];
                if(vis[z])continue;
                if(mp[y].count(z))
                {
                    xu[1]=x;xu[2]=y;xu[3]=z;
                    sort(xu+1,xu+3+1);
                    ans-=A*(xu[1]-1)+B*(xu[2]-1)+C*(xu[3]-1);
                }
            }
        }
    }
    for(int i=0;i<b.size();i++)
    {
        for(int j=i+1;j<b.size();j++)
        {
            x=b[i];y=b[j];
            if(mp[x].count(y)==0)continue;
            for(int k=j+1;k<b.size();k++)
            {
                z=b[k];
                if(mp[x].count(z)&&mp[y].count(z))
                {
                    xu[1]=x;xu[2]=y;xu[3]=z;
                    sort(xu+1,xu+3+1);
                    ans-=A*(xu[1]-1)+B*(xu[2]-1)+C*(xu[3]-1);
                }
            }
        }
    }
    cout<<ans;
    return 0;
}
/*
4 3
2 3 4
0 1
1 2
2 0
*/

有向图的三元环

有向图的三元环和无向图的不一样，一般是用bitset做。

时间复杂度：

题目:CF117C

一个tournament是一个没有自环的有向图，同时，每两个点之间有一条边连接。这就是说，对于两个点u，v（u≠v），有一条从u到v的边或一条从v到u的边。

给你一个tournament，请找出一个长度为3的环。

题解：

都已每个点都用bitset记录他的入点，出点。

#include
using namespace std;
const int N=5005;
int n,x;
bitsetxu,ru[N],chu[N];
inline int read()
{
    int res=0;
    char c;
    c=getchar();
    while(!isdigit(c))c=getchar();
    res=c-48;
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            x=read();
            if(x==1)
            {
                ru[i][j]=1;
                chu[j][i]=1;
            }
        }
    for(int i=n;i;i--)
        for(int j=n;j;j--)
            if(i!=j&&ru[i][j]==1)
            {
                xu=chu[i]&ru[j];
                if(xu.count()==0)continue;
                printf("%d %d %d",i,j,xu._Find_first());
                return 0;
            }
    cout<<-1;
}
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
【2021】智加科技校招技术岗编程题汇总
2022年星环科技秋招笔试算法题
小红书24秋招后端开发
全部 >
面经
面试常考问题整理
面试真题：经典海量数据处理题最详解析（下）
腾讯三面已上岸
0928携程笔试题解
全部 >
内推
员工内推码获取
拼多多内推实习&校招
携程内推携程内推码
体验中心实习生招募 - 淘天集团
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(1) 回帖
加载中...
话题 回帖
返回全部帖子

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”