CF1394B-Boboniu Walks on Graph

2020-08-13 约 959 字预计阅读 2 分钟次阅读

CF1394B-Boboniu Walks on Graph

题目:

题目描述:

Boboniu has a directed graph with $ n $ vertices and $ m $ edges.

The out-degree of each vertex is at most $ k $ .

Each edge has an integer weight between $ 1 $ and $ m $ . No two edges have equal weights.

Boboniu likes to walk on the graph with some specific rules, which is represented by a tuple $ (c_1,c_2,\ldots,c_k) $ . If he now stands on a vertex $ u $ with out-degree $ i $ , then he will go to the next vertex by the edge with the $ c_i $ -th $ (1\le c_i\le i) $ smallest weight among all edges outgoing from $ u $ .

Now Boboniu asks you to calculate the number of tuples $ (c_1,c_2,\ldots,c_k) $ such that

$ 1\le c_i\le i $ for all $ i $ ( $ 1\le i\le k $ ).
Starting from any vertex $ u $ , it is possible to go back to $ u $ in finite time by walking on the graph under the described rules.

输入格式:

The first line contains three integers $ n $ , $ m $ and $ k $ ( $ 2\le n\le 2\cdot 10^5 $ , $ 2\le m\le \min(2\cdot 10^5,n(n-1) ) $ , $ 1\le k\le 9 $ ).

Each of the next $ m $ lines contains three integers $ u $ , $ v $ and $ w $ $ (1\le u,v\le n,u\ne v,1\le w\le m) $ , denoting an edge from $ u $ to $ v $ with weight $ w $ . It is guaranteed that there are no self-loops or multiple edges and each vertex has at least one edge starting from itself.

It is guaranteed that the out-degree of each vertex is at most $ k $ and no two edges have equal weight.

输出格式:

Print one integer: the number of tuples.

样例:

样例输入 1:

样例输出 1:

1
2

样例输入 2:

样例输出 2:

1
1

样例输入 3:

样例输出 3:

1
1

思路:

实现:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102

#include <bits/stdc++.h>
using namespace std;
#define Set(a) memset(a, 0, sizeof(a))
#define F(i, a, b) for (register int i = a, i##end = b; i <= i##end; ++i)
#define UF(i, a, b) for (register int i = a, i##end = b; i >= i##end; --i)
#define openf(a)                   \
    freopen(#a ".in", "r", stdin); \
    freopen(#a ".out", "w", stdout)
#define re register
#define ri re int
#define il inline
typedef long long ll;
typedef unsigned long long ull;
template <typename T>
inline T rd(T &x)
{
    T f = 1;
    x = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            f = -1;
    for (; isdigit(c); c = getchar())
        x = (x << 3) + (x << 1) + (T)(c - '0');
    x *= f;
    return x;
}
ll rd()
{
    ll x;
    rd(x);
    return x;
}
const int inf = 1 << 30;

ll ok[50];
ll rem = 0;
int change[10][10], x[50], y[50];
const int N = 200005;
ll a[N];
int u[N], v[N], w[N];
vector<pair<int, int>> to[N];
int ans = 0, n, m, k;
int chs[10];
void dfs(int pos)
{
    if (pos > k)
    {
        ++ans;
        //F(i,1,k) printf("%d ",chs[i]);puts("");
        return;
    }
    ll tmp = rem;
    F(i, 1, pos)
    {
        rem = tmp;
        if ((rem >> change[pos][i]) & 1)
            continue;
        chs[pos] = i;
        rem |= ok[change[pos][i]];
        dfs(pos + 1);
    }
}
vector<int> from[N];
int main()
{
    F(i, 1, 9)
    F(j, 1, i)
    change[i][j] = i * (i - 1) / 2 + j,
    x[i * (i - 1) / 2 + j] = i, y[i * (i - 1) / 2 + j] = j;
    n = rd();
    m = rd();
    k = rd();
    F(i, 1, m)
    {
        rd(u[i]);
        rd(v[i]);
        rd(w[i]);
        to[u[i]].push_back(make_pair(w[i], i));
    }
    F(i, 1, n)
    sort(to[i].begin(), to[i].end());
    //F(i,1,n) {printf("%d:",i);F(j,0,to[i].size()-1) printf("%d ",v[to[i][j].second]);puts("");}
    F(i, 1, n)
    F(j, 0, to[i].size() - 1)
    a[v[to[i][j].second]] |= (1ll << change[to[i].size()][j + 1]),
        from[v[to[i][j].second]].push_back(change[to[i].size()][j + 1]);
    F(i, 1, n)
    sort(from[i].begin(), from[i].end());
    F(i, 1, n)
    F(j, 1, (int)from[i].size() - 1)
    if (from[i][j - 1] == from[i][j])
        rem |= 1ll << from[i][j];
    F(i, 1, n)
    F(j, 1, 45)
    if ((a[i] >> j) & 1)
        ok[j] |= (a[i] ^ (1ll << j));
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

目录

CF1394B-Boboniu Walks on Graph

CF1394B-Boboniu Walks on Graph

题目:

题目描述:

输入格式:

输出格式:

样例:

样例输入 1:

样例输出 1:

样例输入 2:

样例输出 2:

样例输入 3:

样例输出 3:

思路:

实现: