BZOJ 3498: PA2009 Cakes 一类经典的三元环计数问题

首先引入一个最常见的经典三元环问题。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;

vector <int> g[maxn], low, high;

map <int, int> mp[maxn];

int n, m, in[maxn], vis[maxn];

int main()

{

    scanf("%d %d", &n,&m);

    for(int i=1; i<=m; i++){

        int x,y;

        scanf("%d %d", &x,&y);

        g[x].push_back(y);

        g[y].push_back(x);

        mp[x][y] = 1;

        mp[y][x] = 1;

        in[x]++;

        in[y]++;

    }

    for(int i=1; i<=n; i++){

        if(in[i]<=sqrt(m)) low.push_back(i);

        else high.push_back(i);

    }

    int ans = 0;

    memset(vis, false, sizeof(vis));

    for(int i=0; i<low.size(); i++){

        int x = low[i];

        vis[x] = 1;

        for(int j=0; j<g[x].size(); j++){

            int y = g[x][j];

            if(vis[y]) continue;

            for(int k=j+1; k<g[x].size(); k++){

                int z = g[x][k];

                if(vis[z]) continue;

                if(mp[y].count(z)) ans++;

            }

        }

    }

    for(int i=0; i<high.size(); i++){

        for(int j=i+1; j<high.size(); j++){

            int x, y, z;

            x = high[i];

            y = high[j];

            if(mp[x].count(y)==0) continue;

            for(int k=j+1; k<high.size(); k++){

                z = high[k];

                if(mp[y].count(z)&&mp[x].count(z)) ans++;

            }

        }

    }

    printf("%d\n", ans);

    return 0;

}

BZOJ 3948

//BZOJ 3498

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;

typedef long long LL;

struct node{

    int val,id;

    node(){}

    node(int val,int id):val(val),id(id){}

    bool operator<(const node &rhs)const{

        return val>rhs.val;

    }

}a[maxn];

vector <int> G[maxn];

map <int, int> mp[maxn];

int Rank[maxn], out[maxn], linker[maxn];

int n, m;

int main()

{

    scanf("%d %d", &n,&m);

    for(int i=1; i<=n; i++){

        scanf("%d", &a[i].val);

        a[i].id = i;

    }

    sort(a+1, a+n+1);

    for(int i=1; i<=n; i++) Rank[a[i].id] = i;

    for(int i=1; i<=m; i++){

        int x, y;

        scanf("%d %d", &x,&y);

        if(Rank[x]<Rank[y]){

            G[x].push_back(y), out[x]++, mp[x][y]=1;

        }else{

            G[y].push_back(x), out[y]++, mp[y][x]=1;

        }

    }

    LL ans = 0;

    for(int i=1; i<=n; i++){

        int x = a[i].id, y;

        for(int j=0; j<G[x].size(); j++){

            linker[G[x][j]] = x;

        }

        for(int j=0; j<G[x].size(); j++){

            y = G[x][j];

            if(out[y]>sqrt(m)+1){

                for(int k=0; k<G[x].size(); k++){

                    int z = G[x][k];

                    if(mp[y].count(z)) ans += a[i].val;

                }

            }else{

                for(int k=0; k<G[y].size(); k++){

                    int z = G[y][k];

                    if(linker[z] == x) ans += a[i].val;

                }

            }

        }

    }

    printf("%lld\n", ans);

    return 0;

}