自动搬运

查看原文

来自洛谷，原作者为

	ker_xyxyxyx_xxs 最是人间留不住 朱颜辞镜花辞树

搬运于2025-08-24 22:24:15，当前版本为作者最后更新于2021-07-14 21:59:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}