题解 | 统计个数

首先读入边，节点个数n<=200，因此用邻接矩阵存储比较方便，存在u->v的一条双向边，我们就让邻接矩阵g[u][v]=g[v][u]=1。

然后按照题目要求进行统计，记cnt1为"三角"的数量，cnt2为"线"的数量，考虑枚举a,b,c，枚举到b的时候，要求b!=a且a->b有边，枚举到c的时候，要求c!=a且c!=b且b->c有边，这时已经满足了线的要求，cnt2++，再判断是否c->a存在一条边，如果存在，则cnt1++。时间复杂度为O(n^3)，n最大200，大概是8E6的数据量，不会超时。

枚举完我们发现我们重复统计了的"三角"和"线"的数量，"线"重复统计了两次，"三角"重复统计了六次，而答案要我们输出的是三倍"三角"的数量除以"线"的数量，我们只需要最后一起约分一下即可，就不需要先对cnt1 /= 2，cnt2 /= 2再进行约分了。

对于约分，具体来说就是我们需要分别对分母和分子除以它们的最大公因数。求最大公因数，可以用辗转相除法手写一个gcd函数，也可以使用C++17 <numeric>头文件中新增的std::gcd函数直接求。

最后特判一下，分子为0的情况，直接输出"0/1"即可。

#include <iostream>
#include <vector>
#include <numeric>

void solve(){
  int n,m;
  std::cin >> n >> m;

  auto g = std::vector(n+1,std::vector<int>(n+1));
  for(int i = 0; i < m; i++){
    int u,v;
    std::cin >> u >> v;

    g[u][v] = 1;
    g[v][u] = 1;
  }

  int cnt1 = 0,cnt2 = 0;
  for(int a = 1; a <= n; a++){
    for(int b = 1; b <= n; b++){
      if(b==a || g[a][b]==0){
        continue;
      }
      for(int c = 1; c <= n; c++){
        if(c==a || c==b || g[b][c]==0){
          continue;
        }
        cnt2++;

        if(g[c][a]){
          cnt1++;
        }
      }
    }
  }

  if(cnt1 == 0){
    std::cout << "0/1\n";
    return;
  }

  int gcd = std::gcd(cnt1,cnt2);

  std::cout << cnt1/gcd << "/" << cnt2/gcd << "\n";
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int T = 1;
  std::cin >> T;
  for(; T--;){
    solve();
  }
}