题目链接：这里 题意：给了一个有向图，问有多少个点对(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; }