CF51E题解

· · 题解

【分析】

CF官方题解是俄语的，笔者用百度翻译看了一下，大概意思好像是枚举三个点，剩下的交给预处理的东西来解决。然而百度翻译俄语实在太毒瘤了，翻译了也看不太懂，所以来看看我的题解吧。

这是个有点烦人的计数问题，意思是给你一个无向图（无重边，无自环），求五元环的数量。

我的做法是枚举一个顶点 x，和边 e，设 e 的两端点分别是 a 和 b。每次把答案加上 x 到 a 长度为 2 且不经过 b 的路径数乘以 x 到 b 长度为 2 且不经过 a 的路径数。

乍一看这样统计出来的数量除以 5 就是答案了，然而要考虑 x 与另一个点 y 相连，y 又同时连着 a 和 b 的情况。{x,y,a,b,y} 不是一个合法的五元环（但会被上述算法统计到），而是一个三元环 {y,a,b} 加一条从 x 到 y 的边 。

所以答案要减掉“三元环加一条边”这种结构的数量。我们还是枚举点 x 和边 e（e 连接着 a 和 b），如果 x 同时与 a 和 b 相连，则答案减掉 x 的度数减 2。最终答案要除以 5。

【代码注意事项】

先计算每一对点之间长度为 2 的路径数。这一过程不要用邻接链表，应该用邻接矩阵，否则会超时。

【代码】

#include <bits/stdc++.h>

typedef long long ll;
const int N=702;
int n,m;

struct Graph
{
    int cnt,deg[N];
    bool am[N][N];
    ll p2c[N][N];
    Graph()
    {memset(p2c,0,sizeof(p2c)); memset(am,0,sizeof(am)); memset(deg,0,sizeof(deg));}
    void addEdge(int x,int y)
    {
        am[x][y]=true;
        deg[x]++;
    }
    void getP2c(int x)
    {
        for (register int y=1;y<=n;y++) if (am[x][y])
            for (register int z=1;z<=n;z++)  if (am[y][z])
                p2c[x][z]++;
    }
    ll solve1()
    {
        ll res=0;
        for (int i=1;i<=n;i++) getP2c(i);
        for (int a=1;a<n;a++)
            for (int b=a+1;b<=n;b++) if (am[a][b])
                for (int j=1;j<=n;j++)
                {
                    if (a==j || b==j) continue;
                    res+=(p2c[j][a]-am[j][b])*(p2c[j][b]-am[j][a]);
                }
        return res;
    }
    ll solve2()
    {
        ll res=0;
        for (int a=1;a<n;a++)
            for (int b=a+1;b<=n;b++) if (am[a][b])
                for (int j=1;j<=n;j++)
                {
                    if (a==j || b==j) continue;
                    res+=(am[a][j]&&am[b][j])?deg[j]-2:0;
                }
        return res;
    }
} gra;
int read()
{
    char ch=getchar(); int res=0;
    while (ch<'0'||'9'<ch) ch=getchar();
    while ('0'<=ch&&ch<='9') res*=10,res+=ch-'0',ch=getchar();
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int a=read(),b=read();
        gra.addEdge(a,b); gra.addEdge(b,a);
    }
    ll ans=(gra.solve1()-gra.solve2())/5;
    std::cout<<ans<<std::endl;
    return 0;
}