题目链接:这里
题意:给了一个有向图,问有多少个点对(a, b, c, d)满足a->b->d并且a->c->d,求组成这样的菱形的个数。
解法:水题,对每个点aBFS标记,最后那些对于每个点来说标记了2次以上的肯定就是d点。
复杂度O(n*m)

//CF 489D

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3010;
const int maxm = 30010;
int n, m, edgecnt, head[maxn], vis[maxn];
long long ans;
struct edge{
    int v, nxt;
    edge(){}
    edge(int v, int nxt) : v(v), nxt(nxt) {}
}E[maxm];
void init(){
    edgecnt = 0;
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v){
    E[edgecnt].v = v, E[edgecnt].nxt = head[u], head[u] = edgecnt++;
}
void bfs(int u){
    memset(vis, 0, sizeof(vis));
    queue <int> que;
    vis[u] = 1;
    for(int i = head[u]; ~i; i = E[i].nxt){
        int v = E[i].v;
        if(v == u) continue;
        que.push(v);
    }
    while(!que.empty()){
        int now = que.front(); que.pop();
        for(int i = head[now]; ~i; i = E[i].nxt){
            int v = E[i].v;
            if(v != u) vis[v]++;
        }
    }
    for(int i = 1; i <= n; i++){
        if(vis[i] >= 2){
            ans += 1LL*(vis[i])*(vis[i]-1)/2;
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    init();
    for(int i = 1; i <= m; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
    }
    ans = 0;
    for(int i = 1; i <= n; i++) bfs(i);
    printf("%lld\n", ans);
    return 0;
}