CF51E Pentagon 题解

这是一道很有趣的图论题。

题意简述：

给定一个无向图，求五元环的个数，相同元素的环只算一个。

假如使用邻接表？

枚举五个点？深度过大，最劣的复杂度为 O(m^5)=O(n^{10})O(m5)=O(n10) 无法承受。

改成邻接矩阵呢？复杂度为 O(n^5)O(n5) 也无法承受。

考虑 DP，我们设 a_{i,j,k}ai,j,k​ 为 ii 到 jj 之间距离为 kk 的路径的个数。

显然，DP 方程为：

a_{i,j,k}=\sum_{t=1}^n a_{i,t,1}\times a_{t,j,k-1}ai,j,k​=t=1∑n​ai,t,1​×at,j,k−1​

根据乘法原理，枚举中间点，路径的个数就是两边的乘积。

因为我们只用求五元环，只用枚举 22 到 33 的情况再拼接。

这部分的代码长这样。

for(int t=2;t<=3;t++){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                a[i][j][t]+=a[i][k][1]*a[k][j][t-1];
            }
        }
    }
}

最后我们统计答案：

一条去路长度为 22 的方案数，回路长度为 33 的方案数。

同样根据乘法原理得到答案。

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        ans+=a[i][j][2]*a[i][j][3];
    }
}

因为是双向边，并且是五元环，每个点来回都会被算一次，所以答案要除以 1010。

结束了？

没有，因为是无向图，所以很有可能出现一个三元环加上一条无向边连着。

如何解决？

我们只需要枚举任意三元环，然后求出三个点的度，他们之间形成的假五元环的个数，就是他们度数和减去 33。

因为每个点和另一个点连接，度数都会增加。于是一个三元环内部会形成三个假五元环。外部再向三元环连接，每连接一个就会将答案增加 11，被连接个数即为度数。

#include<cstdio>
#include<algorithm>
#define N 1145
using namespace std;
int n,m,a[N][N][4],in[N];
long long ans;
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int aa,b;
        scanf("%d%d",&aa,&b);
        a[aa][b][1]++;a[b][aa][1]++;
        in[aa]++,in[b]++;
    }
    for(int t=2;t<=3;t++){
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    a[i][j][t]+=a[i][k][1]*a[k][j][t-1];
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            ans+=a[i][j][2]*a[i][j][3];
        }
    }
    ans/=10;
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            if(!a[i][j][1])continue;
            for(int k=1;k<j;k++){
                if(!a[j][k][1])continue;
                if(!a[i][k][1])continue;    
                ans-=in[i]+in[j]+in[k]-3;
            }       
        }
    }
    printf("%lld",ans);
    return 0;
}