[Codeforces]1394B – Boboniu Walks on Graph
本文最后更新于 154 天前,其中的信息可能已经有所发展或是发生改变。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。

原文链接:https://www.codein.icu/cf1394b/

题意

每个点有若干条带权边与之相连,每条边边权都不同。求有多少合法的 $c$ 数组满足 $1 \le c_i \le i$,使得从任意点开始,度为 $i$ 的点经过与之相连的第 $c_i$ 条边的路径能够返回它本身。

解法

如果满足,整张图一定是一个环,且 $1,2,3,\ldots,n$ 都出现一次。设 $next(i,j)$ 为点 $i$ 边权第 $j$ 小的边通向的点,$next(i,c_{deg(i)})$ 恰好遍历 $1,2,3,\ldots,n$,即可满足条件。
如果直接枚举 $c$ 数组,然后暴力检查,复杂度是 $k!n$ 的,无法通过。枚举 $c$ 数组的复杂度无法省去,考虑更快地检查是否符合。
可以预处理出 $c_i = j$ 时,对应的 $next(k,c_{deg(k)} = j) (deg(k) = i)$ 的点集,记为 $S(i,j)$,那么满足的条件可以等价为所有 $S(i,c_i)$ 的并集为 $1,2,3,\ldots,n$,考虑如何快速取并、判断。
说到集合就令人想到 bitset,显然可以用 $S(i,j)$ 的每位来代表是否包含某点,然后或和检查即可。但这复杂度依然是 $O(n)$ 单次的,尽管常数较小依然过不掉。
于是就有哈希方法做。考虑如何设计,能让一个集合对应的哈希值不同,并且满足可加性。
首先,集合之间两两无交集,一旦有交集就无法遍历 $n$ 个点。那么两个无交集集合的可加哈希,用和、积的形式都是可行的。
例如给每个点赋一个值,定义集合的哈希值为其中点权相加,合并两个集合只需要将两集合哈希值相加即可。当给点赋值为 $2^(i-1)$ 时,其实等效于 bitset。
可以选择随机给点赋初值,预处理出 $S(i,j)$ 的哈希值,然后利用哈希就可以做到 $O(k)$ 的检查了。
总复杂度 $O(n + k!k)$

代码

#include <algorithm>
#include <cstdio>
#include <ctime>
#include <ctype.h>
#include <vector>

using namespace std;
const int bufSize = 1e6;
#define DEBUG
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc())
        if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2e5 + 100;
int n, m, k;
int sum;
int a[maxn];
int U[maxn], V[maxn];
vector<int> E[maxn];
int val[10][10];
int c[10], ans;
void dfs(int x)
{
    if (x == k + 1)
    {
        int tsum = 0;
        for (int i = 1; i <= k; ++i) tsum += val[i][c[i]];
        if (sum == tsum) ++ans;
        return;
    }
    for (int i = 1; i <= x; ++i) c[x] = i, dfs(x + 1);
}
int main()
{
    srand(time(0));
    read(n), read(m), read(k);
    for (int i = 1; i <= n; ++i) sum += (a[i] = rand());
    for (int i = 1; i <= m; ++i)
    {
        int a, b, c;
        read(a), read(b), read(c);
        U[c] = a, V[c] = b;
    }
    for (int i = 1; i <= m; ++i) E[U[i]].push_back(V[i]);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= (int)E[i].size(); ++j)
            val[E[i].size()][j] += a[E[i][j - 1]];
    dfs(1);
    printf("%d\n", ans);
    return 0;
}
本文标题:[Codeforces]1394B – Boboniu Walks on Graph
本文作者:Clouder
本文链接: https://www.codein.icu/cf1394b/
转载请标明。
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇