题目传送门

Description

给一个无向简单图,每个点有点权,求所有本质不同的四元环的权值和。

$n,m<=1e5$

Solution

1

考虑折半搜索,每次只搜两层,记录路径的权值以及出现的次数cnt。

具体怎么操作呢?

上图:

对于一个 $u -> w$ 我们要记录如上图的 $cnt,s$ 数组,这样才方便计数。

这是 $O(n^2)$ 的。

2

如何优化?

其实我们可以按照度数排个序,度数大的优先扩展。

对于选择的每一个度数小于 $\sqrt{m}$ 的点,他向外会扩展最多 $sqrt(m)$ 次。对于度数大于 $\sqrt{m}$ 的点,他会向外扩展多次,但是由于所有点的度数之和不能超过 $2$ 倍的 $m$ ,所以单次均摊是 $m$ 次扩展,这样的点不会超过 $\sqrt{m}$ 个,因为所有点的度数之和等于 $2m$ 。那么总时间复杂度就为 $O(m\sqrt{m})$

Code(建议和调试代码一起食用)

/*
 * @Name: C
 * @Author: Lovely_XianShen
 * @Date: 2019-11-02 18:25:16
 * @Aqours!Sunshine!!
 */
#include<bits/stdc++.h>
#define maxn 100005

using namespace std;

struct ios {
    inline char read() {
        static const int IN_LEN = 1 << 18 | 1;
        static char buf[IN_LEN], *s, *t;
        return (s == t) && (t = (s = buf) + fread(buf, 1, IN_LEN, stdin)), s == t ? -1 : *s++;
    }

    template <typename _Tp> inline ios &operator >> (_Tp &x) {
        static char c11, boo;
        for (c11 = read(), boo = 0; !isdigit(c11); c11 = read()) {
            if (c11 == -1)return *this;
            boo |= c11 == '-';
        }
        for (x = 0; isdigit(c11); c11 = read())x = x * 10 + (c11^'0');
        boo &&(x = -x);
        return *this;
    }
} io;

const int mod = 1e9 + 7;

int n, m, a[maxn], d[maxn], id[maxn], rk[maxn], s[maxn], cnt[maxn], ans;

vector<int>G[maxn], F[maxn];

bool cmp(int i, int j) {
    return d[i] == d[j] ? i < j : d[i] < d[j];
}

int main() {
    io >> n >> m;
    for (int i = 1; i <= n; i++)
        io >> a[i];
    for (int i = 1, x, y; i <= m; i++)
        io >> x >> y, G[x].push_back(y), G[y].push_back(x);
    for (int i = 1; i <= n; i++)
        d[id[i] = i] = G[i].size();
    sort(id + 1, id + 1 + n, cmp);
    for (int i = 1; i <= n; i++)
        rk[id[i]] = i;
//    for (int i = 1; i <= n; i++)
//        cout << rk[i] << endl;
    for (int i = 1; i <= n; i++)
        for (int j : G[i])
            if (rk[j] > rk[i]) F[i].push_back(j);
    for (int u = 1; u <= n; u++) {
        for (int v : G[u])
            for (int w : F[v]) {
                cout << "u=" << u << " v=" << v << " w=" << w << endl;

                if (rk[w] > rk[u]) {

                    ans = (ans + s[w] + 1ll * cnt[w] * a[v]) % mod, s[w] = (1ll * s[w] + a[u] + a[w] + a[v]) % mod, cnt[w]++;

                    cout << "u=" << u << " v=" << v << " w=" << w << " ans=" << ans << " s[w]=" << s[w] << " cnt[w]" << cnt[w] << endl;

                }
            }
        for (int v : G[u])
            for (int w : F[v])
                if (rk[w] > rk[u]) {
                    s[w] = cnt[w] = 0;
                    cout << "s[w]=" << s[w] << " cnt[w]" << cnt[w] << endl;
                }
    }
    printf("%d\n", ans);
    return 0;
}

/*
Pretest - 1.in
5 6
1 2 3 4 5
1 2
2 5
1 3
3 5
1 4
4 5
Pretest - 1.out
36
*/