[杂题 计数 图论] Codeforces 51E. Pentagon

挺烦的题…..很容易wa…
总之就是求出 $B_{i,j}$ 表示 $i$ 到 $j$ ,走两步的方案，$C_{i,j}$ 表示走三步。
然后 $\sum B_{i,j}*C_{i,j}$。然后会有不合法的和重复的…
不合法的大概是 一个三角形多出一个脚…或者就是一个三角形… 在纸上大力分类讨论一下，把它们都扣去就好了。
参考了网上dalao的实现。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL; 
const int maxn=705;
int n,m,d[maxn],A[maxn][maxn],B[maxn][maxn],C[maxn][maxn];
LL ans;
int main(){
    freopen("cf51E.in","r",stdin);
    freopen("cf51E.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y; scanf("%d%d",&x,&y);
        d[x]++; d[y]++;
        A[x][y]=A[y][x]=1;
    }
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++) B[i][j]+=A[i][k]*A[k][j];
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++) C[i][j]+=A[i][k]*B[k][j];
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++) ans+=(LL)B[i][j]*C[i][j];
    ans/=10;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=i-1;j++)
      for(int k=1;k<=j-1;k++) if(A[i][j]&&A[i][k]&&A[j][k]) ans-=d[i]+d[j]+d[k]-3;
    printf("%lld\n",ans); 
    return 0;
}