P6815 [PA2009]Cakes

· · 题解

P6815 [PA2009]Cakes

题目直接点出三元环了，简单介绍一下。

定义：三元环是指对于图上的三个点，两两点之间都直接有边相连，这三个点组成的环就是三元环。

三元环的计数方法：记录图中每个点的度数，对于每条边将它定向。对于一条边，将度数大的点指向度数小的点，如果度数相同就将编号小的点指向编号大的点。计数时枚举每个点，对于每个点 x 枚举它的出边，并将出边指向的点 y 打标记，对于所有出边指向的点 y 再枚举出边，如果这个出边指向的点 z 被打了标记，那么 x,y,z 就组成了一个三元环。时间复杂度为 O(m \cdot \sqrt{m}) 。

性质：

1、这一定是一个有向无环图。

2、每个三元环只会被统计一次。

（怎么证明请自己思考）

这个题直接按照上述方法计算即可。

AC 100pts Code


# include <iostream>
# include <cstdio>
# include <vector>
using namespace std;
static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
template<typename item>
inline void read(register item &x)
{
    x=0;register char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
static char cc[10000];
template<typename item>
inline void print(register item x)
{ 
    register long long len=0;
    while(x)cc[len++]=x%10+'0',x/=10;
    while(len--)putchar(cc[len]);
}
const int maxn = 2e6 + 5;
typedef long long ll;
ll ans = 0;
int n , m;
int w[maxn];
typedef struct {
    int x , y;
}ed;
ed N[maxn];
int x , y;

vector<int> g[maxn];
int deg[maxn];
int mark[maxn];
int main() {
    read(n);
    read(m);
    for (int i = 1 ; i <= n ; i ++) {
        read(w[i]);
    }
    for (int i = 1 ; i <= m ; i ++) {
        read(x);
        read(y);
        deg[x] ++;
        deg[y] ++;
        N[i].x = x;
        N[i].y = y;
    }
    for (int i = 1 ; i <= m ; i ++) {
        int x = N[i].x , y = N[i].y;
        if (deg[x] > deg[y] || (deg[x] == deg[y] && x < y)) swap(x , y);
        g[x].push_back(y);
    }

    for (int x = 1 ; x <= n ; x ++) {
        for (int i = 0 ; i < g[x].size() ; i ++) {
            mark[g[x][i]] = x;
        }
        for (int i = 0 ; i < g[x].size() ; i ++) {
            int e = g[x][i];
            for (int j = 0 ; j < g[e].size() ; j ++) {
                int endd = g[e][j];
                if (mark[endd] == x) ans += max(w[x] , max(w[e] , w[endd]));
            }
        }
    }
    printf("%lld\n" , ans);
    fwrite(obuf,p3-obuf,1,stdout);
    return 0;
}