[bzoj3498]cakes(三元环)_寻找所有三元环

题面
题意基本就是找出所有三元环
$n<=100000 m <=250000$

我竟然才会这个鬼东西 太菜了qwq
说起来我前几天才知道中国剩余定理2333333

先把双向边，变成单向边
由度数小的点，连向度数大的点，如果度数相等 从小点连向大点

这样之后，每个点连出去的边小于$sqrt(m)$

因为原本度数大于$sqrt(m)$的点小于$sqrt(m)$个，又因为度数大于$sqrt(m)$只会连度数更大的，所以度数大于$sqrt(m)$的点最多只会连出去$sqrt(m)$条有向边。

所以只需从一个点枚举任意两条边，再判断连出去的两个点是否有边即可(hash)，复杂度$O(m*sqrt(m))$

然后我hash TLE了…

换了种写法，枚举边，再枚举这条边两边的点，遍历这两个点连出去的所有点，打个标记，就能去掉hash了

---

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
class Dread{
    private:
        bool isdigit(char ch) { return ch >= '0' && ch <= '9'; }
        void Getchar(int &tmp){
            char ch; tmp = 0; bool b = true;
            while (ch = getchar()){
                if (ch == '-') b = false;
                if (isdigit(ch)) break;
            }
            for (; isdigit(ch); ch = getchar()) tmp = tmp * 10 + ch - '0';
            if (!b) tmp = -tmp;
        }
    public:
        int Int(){ int x; Getchar(x); return x; }
}Read;
const int maxn = 1e5 + 10;
const int maxm = 2.5e5 + 10;
vector<int> g[maxn];
struct {
    int x, y;
}edge[maxm];
int n, m;
int a[maxn], id[maxn];
int d[maxn];
void init(){
    n = Read.Int(), m = Read.Int();
    for (int i = 1; i <= n; i ++)
        a[i] = Read.Int();
    for (int i = 1; i <= m; i ++){
        edge[i].x = Read.Int(), edge[i].y = Read.Int();
        d[edge[i].x] ++, d[edge[i].y] ++;
    }
}
bool cmp(int x, int y){
    if (d[x] != d[y]) return d[x] < d[y];
    return x < y;
}
int vis[maxn];
void work(){
    for (int i = 1; i <= m; i ++){
        if (!cmp(edge[i].x, edge[i].y))
            swap(edge[i].x, edge[i].y);
        g[edge[i].x].push_back(edge[i].y);
    }
    ll ans = 0;
    for (int i = 1; i <= m; i ++){
        int tmp = max(a[edge[i].x], a[edge[i].y]);
        for (int asd = 0; asd < g[edge[i].x].size(); asd ++)
            vis[g[edge[i].x][asd]] = i;
        for (int asd = 0; asd < g[edge[i].y].size(); asd ++)
            if (vis[g[edge[i].y][asd]] == i)
                ans += max(a[g[edge[i].y][asd]], tmp);
    }
    cout <<ans <<endl;
}
int main(){
    init();
    work();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63