1 条题解

  • 0
    @ 2024-7-26 16:23:59

    可以枚举每条边上的两个点,作为路径中间的两个点,那么只需要计算两个点的度相乘的结果即可。(需要去掉和边的另一个端点相连的度,因此度数需要减1)

    核心代码
    
    #include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 10005;
    const int MAXM = 100005;
    int n, m, u[MAXM], v[MAXM], deg[MAXN];
    long long ans;
    int main()
    {
        cin >> n >> m;
        for (int i = 1; i <= m; i++) {
            cin >> u[i] >> v[i];
            deg[u[i]]++;
            deg[v[i]]++;
        }
        for (int i = 1; i <= m; i++)
            ans += (deg[u[i]] - 1) * (deg[v[i]] - 1) * 2;
        cout << ans;
    	return 0;
    }
    
    • 1

    信息

    ID
    898
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    (无)
    递交数
    20
    已通过
    11
    上传者