Codeforces 489D(枚举+组合数)

Codeforces 489D
题意：给出$n$点，$m$条有向边，问有多少个如下图的菱形

一个菱形有两条路径组成，如果我们找到$u$到$v$的不同路径数量，就可以用$C_n^2$来计算有几个菱形了。枚举这样的三元组来找路径

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const int MAXN = 3000 + 5;

std::vector<int > G[MAXN];
int n, m;
LL whw[MAXN][MAXN];

void clean() {
    ms(whw, 0);
}
int solve() {
    clean();
    for (int a, b, i = 1; i <= m; i++) scanf("%d%d", &a, &b), G[a].push_back(b);
    for (int u = 1; u <= n; u++) {
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i];
            for (int j = 0; j < (int)G[v].size(); j++) {
                int w = G[v][j];
                whw[u][w]++;
            }
        }
    }
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) if (i != j) {
            ans += whw[i][j] * (whw[i][j] - 1) / 2;
        }
    }
    printf("%lld\n", ans);
    return 0;
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}