OI Problems   关于

三元环计数

三元环指的是一个简单无向图中的一个无序三元组 (u, v, w)(u,\ v,\ w) 使得存在三条边分别连接 (u, v)(u,\ v)，(v, w)(v,\ w) 和 (w, u)(w,\ u)。我们的目标是遍历这些三元环。

首先，给无向边进行定向。规定从度数大的点指向度数小的点，度数相同就从编号小的点指向编号大的点。此时此图是一张有向无环图。

该图没有环的证明

反证法，反设存在环，那么环中的点度数一个比一个大，要形成环，所有点的度数必须相等，但是编号必定不同，矛盾。

所以定向后图肯定不存在环。

枚举 uu 和 uu 指向的点 vv，再在 vv 指向的点中枚举 ww，检验 uu 是否与 ww 相连即可。

时间复杂度 Θ(mm)\Theta(m\sqrt m)（假设 n, mn,\ m 同阶）。

时间复杂度证明

对于定向部分，遍历了所有的边，时间复杂度 Θ(n+m)\Theta(n+m)。

若已经枚举 u, vu,\ v，那么剩下的枚举量为 vv 的出度。

若 vv 的出度 ≤m\leq\sqrt m，由于 uu 的个数至多为 nn，所以这部分时间复杂度为 Θ(nm)\Theta(n\sqrt m)。

若 vv 的出度 >m> \sqrt m，由于 uu 指向 vv，所以 degu≥degvdeg_u \geq deg_v，得出 degu>mdeg_u > \sqrt m，但是总边数只有 mm，所以这样的 uu 的个数至多为 m\sqrt m，故时间复杂度为 Θ(mm)\Theta(m\sqrt m)。

总时间复杂度为 Θ(n+m+nm+mm)=Θ(mm)\Theta(n+m+n\sqrt m+m\sqrt m)=\Theta(m\sqrt m)（假设 n, mn,\ m 同阶）。


题解

考虑枚举结点 ww，那么贡献就是与 ww 相邻的结点的权值两两之积。但是要减去两点已经有边的情况。此情况类似于三元环计数，只需遍历三元环即可。

对于最大值部分，同样考虑直接枚举 ww，再枚举 ww 的相邻结点作为 u, vu,\ v 即可。但是由于我们只需要找到最大值，所以可以按照点权进行排序，从大到小找到第一个合法的三元组即可。而由于只有遇到三元环才会往更小的找，所以时间复杂度等价于三元环个数。

时间复杂度 Θ(mm)\Theta(m\sqrt m)（假设 n, mn,\ m 同阶）。

  代码
// 2023.07.19

#include<bits/stdc++.h>
using namespace std;

int n,m,t,w[30001];
int ans_max=-1; long long ans_sum;

set<pair<int,int> > Edges;
vector<int> unidirEdge[30001];
struct Edge{
    int to,nxt;
}edge[60001];
int cntEdge,head[30001],deg[30001];
void addEdge(int u,int v){
    edge[++cntEdge]={v,head[u]},head[u]=cntEdge;
    Edges.insert({u,v}),deg[u]++;
}

bool comparator(int u,int v){
    return w[u]>w[v];
}

int main(){
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
    }
    for(int i=1;i<=n;i++)
        scanf("%d",w+i);

    for(int i=1;i<=n;i++){
        // 枚举中间的结点
        int tmp[30001]={},total=0;
        for(int j=head[i];j;j=edge[j].nxt)
            tmp[++total]=edge[j].to;
        sort(tmp+1,tmp+1+total,comparator);
        int exitAt=total;
        for(int j=1;j<=exitAt;j++){
            int NodeId=j+1;
            for(;NodeId<=exitAt;NodeId++)
                if(Edges.find({tmp[j],tmp[NodeId]})==Edges.end())
                    break;
            if(NodeId>exitAt)continue;
            ans_max=max(ans_max,w[tmp[j]]*w[tmp[NodeId]]);
            exitAt=NodeId-1;
        }
        long long sum=0;
        for(int j=1;j<=total;j++)
            ans_sum+=sum*w[tmp[j]],
            sum+=w[tmp[j]];
    }
    
    for(int i=1;i<=n;i++)
        for(int j=head[i];j;j=edge[j].nxt)
            if(deg[edge[j].to]>deg[i])
                unidirEdge[i].push_back(edge[j].to);
            else if(deg[edge[j].to]==deg[i]&&edge[j].to>i)
                unidirEdge[i].push_back(edge[j].to);
    for(int i=1;i<=n;i++)
        for(int j :unidirEdge[i])
            for(int k :unidirEdge[j])
                if(Edges.find({i,k})!=Edges.end())
                    ans_sum-=w[i]*w[j]+w[j]*w[k]+w[k]*w[i];
    if(t==1)ans_sum=0;
    if(t==2)ans_max=0;
    printf("%d\n%lld\n",ans_max,ans_sum*2);
    return 0;
}