[BZOJ 3498] [PA 2009] Cakes

墨蓝 2021-12-22 04:09 234阅读 0赞

## Description ##

\\(n\\) 个点 \\(m\\) 条边，每个点有一个点权 \\(a\_i\\)。  
对于任意一个三元环 \\((i,j,k)(i<j<k)\\)，它的贡献为 \\(\\max(a\_i,a\_j,a\_k)\\)，求所有三元环的贡献和。

## Input ##

The first line of the standard input contains two integers n and m (1<=N<=100000,1<=M<=250000) separated by a single space and denoting the number of confectioners at the convention and the number of pairs of them that like each other. The participants of the convention are numbered from 1 to N, The second line contains n integers pi (1<=Pi<=1000000) separated by single spaces and denoting the requirements of respective confectioners for flour (in decagrams). The following m lines contain data about pairs of contestants that like each other. Each of these lines contains two integers ai and bi (1<=ai,bi<=n Ai<>Bi) separated by a single space. They denote that confectioners ai and bi like each other. We assume that all pairs of participants of the convention apart from the ones listed in the input would not like to bake cakes together. Each pair of confectioners appears at most once in the input.

## Output ##

The first and only line of the standard output should contain a single integer - the quantity of flour that will be used by all teams in total, in decagrams.

## Sample Input ##

5 7
    1 5 3 4 2
    1 2
    2 3
    5 2
    4 3
    3 1
    1 4
    5 1

## Sample Output ##

14
    Explanation of the example. The following three-person teams: (1,2,3),(1,2,5) and (1,3,4)require 5, 5 and 4 decagrams of flour to bake the cakes. In total 5+5+4=14 decagrams of flour are required.

## HINT ##

\\(n\\le100000,m\\le250000\\)

## Solution ##

**〖一〗**

将节点按照度数 \\(\\le \\sqrt m\\) 和 \\(> \\sqrt m\\) 分为两类，由于只有 \\(m\\) 条边，因此度数 \\(> \\sqrt m\\) 的点的个数为 \\(O(\\sqrt m)\\)。

对于存在度数 \\(\\le\\sqrt m\\) 的点的三元环，枚举度数 \\(\\le\\sqrt m\\) 的点，再枚举它的两条边，判断这两条边指向的点是否有边相连，这里枚举第一条边相当于枚举图中的所有边，第二条边是度数复杂度，因此时间复杂度为 \\(O(m\\sqrt m)\\)。

对于点的度数均 \\(> \\sqrt m\\) 的三元环，三重循环枚举度数 \\(> \\sqrt m\\) 的点，复杂度 \\(O((\\sqrt m)^3)=O(m\\sqrt m)\\)。

判断两个点之间是否有边相连用 \\(map<pair,bool>\\) 判断就行了。

**〖二〗**

还有一个黑科技做法，将每条边定向，由度数大的点指向度数小的点，如果度数相同就由编号小的点指向编号大的点，显然这样得到的图是不存在环的。

枚举每个点 \\(i\\)，再枚举它的出边，将出边指向的点 \\(j\\) 打上标记，再枚举点 \\(j\\) 的出边，如果此时出边指向的点 \\(k\\) 被打了标记，那么 \\(i,j,k\\) 就组成了一个三元环。这样每个三元环只会被统计一次。

考虑证明时间复杂度。如果一个点的出度 \\(\\le \\sqrt m\\)，指向它的点最多有 \\(n\\) 个，复杂度为 \\(O(n\\sqrt m)\\)；如果一个点的出度 \\(>\\sqrt m\\)，指向它的点的出度一定比它大，最多有 \\(\\sqrt m\\) 个，复杂度为 \\(O(m\\sqrt m)\\)。

**〖三〗**

[HDU 6184 Counting Stars][] 是求 \\(V=(A,B,C,D),E=(AB,BC,CD,DA,AC)\\) 的子图个数。

设 \\(cnt\[i\]\\) 表示第 \\(i\\) 条边在多少个三元环中出现过，求三元环的时候顺便统计出来即可，最后枚举每条边，将 \\(\\large\\binom\{cnt\[i\]\}\{2\}\\) 计入答案。

## Code ##

#include <cstdio> #include <algorithm> const int N = 100005, M = 250005; struct Pair { int u, v; } p[M]; struct Edge { int v, nxt; } e[M]; int a[N], d[N], head[N], tot, f[N], q[N]; long long ans; int read() { int x = 0; char c = getchar(); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return x; } void adde(int u, int v) { e[++tot].nxt = head[u], head[u] = tot, e[tot].v = v; } int main() { int n = read(), m = read(); for (int i = 1; i <= n; ++i) a[i] = read(); for (int i = 1; i <= m; ++i) p[i].u = read(), p[i].v = read(), ++d[p[i].u], ++d[p[i].v]; for (int i = 1; i <= m; ++i) if (d[p[i].u] == d[p[i].v]) p[i].u < p[i].v ? adde(p[i].u, p[i].v) : adde(p[i].v, p[i].u); else d[p[i].u] > d[p[i].v] ? adde(p[i].u, p[i].v) : adde(p[i].v, p[i].u); for (int i = 1; i <= n; ++i) { int t = 0; for (int j = head[i]; j; j = e[j].nxt) f[e[j].v] = i, q[++t] = e[j].v; for (int j = 1; j <= t; ++j) for (int k = head[q[j]]; k; k = e[k].nxt) if (f[e[k].v] == i) ans += std::max(a[i], std::max(a[q[j]], a[e[k].v])); } printf("%lld\n", ans); return 0; }

转载于:https://www.cnblogs.com/fly-in-milkyway/p/10364921.html

[HDU 6184 Counting Stars]: http://acm.hdu.edu.cn/showproblem.php?pid=6184