分治

51Nod 1601 完全图的最小生成树计数

Posted on

分治+字典树+MST 综合好题

标题即题意,但是不一样的是边权是点权的异或。

不可能会出什么边权也是给定的完全图最小生成树计数的啦,现在看来,也算是套路题了。
当然点数不能太多…………

不卡常才是一个好题的前提条件。写 Trie 习惯性用了类,虽然慢了一些,但也不至于太慢。

题意:
给你 n 个点的点权,边权为其异或值,要你求出最小生成树,以及最小生成树的个数。

思路:
这道题的核心思想还是分治。
我们对给定区间的点权进行处理,并假设这个区间的前面 k - 1 位全部相同。那么对于第 k 位,我们根据 01 将其划分为两个集合,这时候两个集合的前 k 位分别相同,再对这两个集合分别进行同样的处理。
其正确性不言而喻。

在处理的过程中,我们需要将两个集合之间建边,因为是MST,所以要找最小的边。将其中一个集合插入 字典树,再让另一个集合的每一个点以常数级别的复杂度去找到最小异或值,再更新答案与边数。
最小生成树的个数只要根据乘法原理将边的数量相乘即可。

AC Code

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;

int n, anscnt, val[maxn], s[maxn], t[maxn];
long long sum;

struct Trie {
    int end[maxn * 30], next[maxn * 30][2];
    int size, root;

    int newNode()
    {
        next[size][0] = next[size][1] = 0;
        end[size++] = 0;
        return size - 1;
    }

    void init()
    {
        size = 0;
        root = newNode();
    }

    void insert(int x)
    {
        int cur = root;
        for (int i = 30, y; i >= 0; i--) {
            y = (x >> i) & 1;
            if (!next[cur][y])
                next[cur][y] = newNode();
            cur = next[cur][y];
        }
        end[cur]++;
    }

    pii search(int x)
    {
        int cur = root, ans = 0;
        for (int i = 30, y; i >= 0; i--) {
            y = (x >> i) & 1;
            if (next[cur][y])
                cur = next[cur][y], ans |= (y << i);
            else
                cur = next[cur][y ^ 1], ans |= ((y ^ 1) << i);
        }
        return make_pair(ans ^ x, end[cur]);
    }
} trie;

inline void read(int& x)
{
    char ch = getchar();
    x = 0;
    while (!(ch >= '0' && ch <= '9'))
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - '0', ch = getchar();
}

int fastPow(int x, int y)
{
    int res = 1;
    while (y) {
        if (y & 1)
            res = 1LL * res * x % mod;
        x = 1LL * x * x % mod, y >>= 1;
    }
    return res;
}

void dac(int l, int r, int dep)
{
    if (l >= r)
        return;
    if (dep < 0) {
        if (r - l + 1 >= 2)
            anscnt = 1LL * anscnt * fastPow(r - l + 1, r - l - 1) % mod;
        return;
    }
    int lc = 0, rc = 0, ans = inf, cnt = 0;
    for (int i = l; i <= r; i++) {
        if ((val[i] >> dep) & 1)
            s[lc++] = val[i];
        else
            t[rc++] = val[i];
    }
    trie.init();
    for (int i = 0; i < lc; i++)
        val[l + i] = s[i];
    for (int i = 0; i < rc; i++) {
        val[l + lc + i] = t[i];
        trie.insert(t[i]);
    }
    pii tmp;
    for (int i = 0; i < lc; i++) {
        tmp = trie.search(s[i]);
        if (ans > tmp.first)
            ans = tmp.first, cnt = tmp.second;
        else if (ans == tmp.first)
            cnt += tmp.second;
    }
    if (cnt) {
        sum += ans;
        anscnt = 1LL * cnt * anscnt % mod;
    }
    dac(l, l + lc - 1, dep - 1);
    dac(l + lc, r, dep - 1);
}

int main()
{
    anscnt = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", val + i);
    dac(1, n, 30);
    printf("%lld\n%d\n", sum, anscnt);
    return 0;
}
最小生成树

HDU 4408 Minimum Spanning Tree

Posted on

真是不容易啊……
最小生成树计数,虽然说觉得以后已经基本不会考到了,但毕竟防范与未然
具体算法我已经在之前一篇算法证明上提到过了,这里是他的矩阵树实现。

这里的代码就暂时作为我的模板了,之后再找题验证一下。

题意:
最小生成树计数裸题

思路:
详见之前一篇证明文章

这里有个地方我一开始不是很明白,就是为什么要用两个并查集来维护。

纸上画了一画,稍微有点理解,简单说就是为了相同边权的边进行缩点,后续的并查集操作就用缩点后的点集,这符合算法的流程和原理。

该代码已经尝试在BZOJ 1016 上 1A ,作为本人模板使用

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)

typedef long long ll;
const int maxn = 105;
const int maxm = 1005;
ll mod, ans;
int n, m;

vector<int> G[maxn];
int root[maxn], vis[maxn], scc[maxn];
int g[maxn][maxn];
ll mat[maxn][maxn];

struct node {
    int u, v, w;
} edges[maxm];

void init()
{
    ans = 1;
    each(i, n + 1) scc[i] = root[i] = i;
    memset(g, 0, sizeof g);
}

int findRoot(int x, int rootAry[])
{
    return rootAry[x] == x ? x : rootAry[x] = findRoot(root[x], rootAry);
}

ll getDet(ll a[][maxn], int n)
{
    range(i, 1, n) range(j, 1, n) a[i][j] = (a[i][j] + mod) % mod;
    ll ret = 1;
    range(i, 1, n - 1)
    {
        range(j, i + 1, n - 1) while (a[j][i])
        {
            ll t = a[i][i] / a[j][i];
            range(k, i, n - 1) a[i][k] = (a[i][k] - a[j][k] * t % mod + mod) % mod;
            swap(a[i], a[j]);
            ret = -ret;
        }
        if (a[i][i] == 0)
            return 0;
        ret = ret * a[i][i] % mod;
    }
    return (ret + mod) % mod;
}

void matrixTree()
{
    range(i, 1, n) if (vis[i])
    {
        G[findRoot(i, root)].push_back(i);
        vis[i] = false;
    }
    range(i, 1, n) if (G[i].size() > 1)
    {
        int sz = G[i].size();
        memset(mat, 0, sizeof mat);
        each(j, sz) range(k, j + 1, sz - 1)
        {
            int u = G[i][j], v = G[i][k];
            if (g[u][v]) {
                mat[k][j] = (mat[j][k] -= g[u][v]);
                mat[k][k] += g[u][v];
                mat[j][j] += g[u][v];
            }
        }
        ans = ans * getDet(mat, G[i].size()) % mod;
        each(j, sz) scc[G[i][j]] = i;
    }
    range(i, 1, n)
    {
        G[i].clear();
        root[i] = scc[i] = findRoot(i, scc);
    }
}

void output()
{
    range(i, 1, n - 1) if (scc[i] != scc[i + 1])
    {
        puts("0");
        return;
    }
    printf("%lld\n", ans % mod);
}

int main()
{
    while (scanf("%d %d %lld", &n, &m, &mod) != EOF && n + m + mod) {
        each(i, m) scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
        sort(edges, edges + m, [](const node& a, const node& b) { return a.w < b.w; });
        init();
        edges[m].w = -1;
        range(i, 0, m)
        {
            if (i && edges[i].w != edges[i - 1].w)
                matrixTree();
            int u = findRoot(edges[i].u, scc), v = findRoot(edges[i].v, scc); //缩点后的点
            if (u != v) {
                vis[u] = vis[v] = true;
                root[findRoot(u, root)] = findRoot(v, root);
                g[u][v]++, g[v][u]++; 
            }
        }
        output();
    }
    return 0;
}

最小生成树

BZOJ 1016 [JSOI2008]最小生成树计数

Posted on

bzoj 第一题,矩阵树算法写起来炒鸡烦,就先去写了一发暴力的……
说是写的,其实基本是看着黄学长的代码敲的……

题意:
最小生成树计数。

思路:
请查阅本人关于最小生成树计数的粗浅证明文章。

注: 这道题你不手写读入会蜜汁WA

#include <bits/stdc++.h>

#define ll long long
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(num, ary) memset((ary), (num), sizeof((ary)))

using namespace std;
const int mod = 31011;
const int maxn = 1005;

struct edge {
    int u, v, w;
    bool operator<(const edge& a) const
    {
        return w < a.w;
    }
} edges[maxn];

struct segment {
    int l, r, num;
} segs[maxn];

int n, m, cnt, tot, sum, ans = 1;
int root[maxn];

inline bool scan_d(int& num)
{
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF)
        return false;
    while (in != '-' && (in < '0' || in > '9'))
        in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else
        num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') {
        num *= 10, num += in - '0';
    }
    if (IsN)
        num = -num;
    return true;
}

int findRoot(int x)
{
    return root[x] == x ? x : findRoot(root[x]);
}

void dfs(int id, int cur, int num)
{
    if (cur == segs[id].r + 1) {
        if (num == segs[id].num)
            sum++;
        return;
    }
    int ru = findRoot(edges[cur].u), rv = findRoot(edges[cur].v);
    if (ru != rv) {
        root[rv] = ru;
        dfs(id, cur + 1, num + 1);
        root[rv] = rv, root[ru] = ru;
    }
    dfs(id, cur + 1, num);
}

int main()
{
    scan_d(n),scan_d(m);
    range(i, 1, m)
        scan_d(edges[i].u),scan_d(edges[i].v),scan_d(edges[i].w);
    each(i, n + 1)
        root[i] = i;
    sort(edges + 1, edges + m + 1);
    range(i, 1, m)
    {
        if (edges[i].w != edges[i - 1].w) {
            segs[cnt].r = i - 1;
            segs[++cnt].l = i;
        }
        int ru = findRoot(edges[i].u), rv = findRoot(edges[i].v);
        if (ru != rv) {
            root[rv] = ru;
            segs[cnt].num++;
            tot++;
        }
    }
    segs[cnt].r = m ;
    if (tot != n - 1) {
        puts("0");
        return 0;
    }
    each(i, n + 1)
        root[i] = i;
    range(i, 1, cnt)
    {
        sum = 0;
        dfs(i, segs[i].l, 0);
        ans = ans * sum % mod;
        range(j, segs[i].l, segs[i].r)
        {
            int ru = findRoot(edges[j].u), rv = findRoot(edges[j].v);
            if (ru != rv)
                root[rv] = ru;
        }
    }
    printf("%d\n", ans);
    return 0;
}
最小生成树

关于最小生成树计数算法的粗浅证明

Posted on

问题描述

最小生成树计数问题是给定一个无向带权图,问你能生成最小生成树的数量为多少。

存在多个最小生成树的原因

出现多棵最小生成树的原因在于,我们存在一些权值相同的边,相互替换之后整张图的联通性不变。

这里你可能会问,为什么权值不同的边就不能替换了呢?

简单证明一下
就拿两两交换的情况来说,因为一一交换显然不成立,如果你还要对此表示质疑我也没办法……

两两交换的情况就是* 存在用两条不是很大也不是很小的边与替代两条极大极小的边的情况。*

稍微专业点的说法就是,存在极小和极大的中间有两条边可以替代两边的边 不仅能保持整张图联通性不变,并且权值和不会增大。

我这里表示,不可能

举个例子,首先 b - c 已经在同一个集合中了。
并且 存在 四条边

  1. a - b 权值为 1
  2. c - d 权值为 100
  3. a - c 权值为 50
  4. c - d 权值为 51

我们要考虑的问题是 能否让 3 边和 4 边去替代 1 边和 2 边
有了数据,这个问题就很显然了,1 边和 2 边根本不可能在最小生成树上,因为不仅 1 边 和 3 边的联通性与之相同,并且权值更小。

同理,我们可以将之拓展到 n >= 3 的情况。

算法引入

最小生成树计数算法是基于克鲁斯卡尔算法的一些操作。

根据以上存在多个最小生成树的原因,我们把最小生成树分成多个权值相同的边的最小生成树,再运用乘法原理计算。

因此在运用克鲁斯卡尔算法的中间过程中,我们需要记录所有相同权值的边,和这些边在整个最小生成树的联通度。
因为在克鲁斯卡尔算法的流程中,每条边都是按照边权排序的,所以我们记录所有相同权值的边只需要记录一个区间即可。
而联通度,只需要在合并操作中进行记录即可。

剩下的关键就是如何求出生成树的数量。(因为权值都已经相同了)

  • 一种暴力的解法就是直接搜索,这个方法复杂度就是相同权值的边数的最大数量的阶乘。搜索途中满足联通性不变则方案数++即可。优点就是写得快,不建议在最大边数大于10的时候使用。
  • 另一种方法是运用矩阵树定理。这种算法写起来很长,但复杂度为 点数 n ^ 3 。
    (这里我不细讲这些)

这个时候有些朋友就会提出这样的困惑,如何保证在每个权值相同的生成树计算过程中,整棵树的桥必定会包含在内
这个问题其实挺煞笔的,我写这个问题主要是我煞笔的被困在这里面一小段时间。

保证整棵树的桥必定会被加入到相应的生成树的原因

再简单证明一下
既然是整棵树的桥,那么也就是权值相同的生成树的桥,所以无论在计算最小生成树的过程中,还是在计算权值相同的生成树的过程中,这条边必定会加入在内。
前者因为不加的话,无法形成生成树。后者则是不满足联通性条件。

最小生成树

HDU4081 Qin Shi Huang’s National Road System

Posted on

传送门

昨天第一次跟两个妹子一起打……真特么那个紧张啊 人生赢家请闭嘴

这题应该是属于我的题目但到最后还是没有A掉的,如果到了现场赛,这样怕是要打铁了……

题意:
给你n个点与其权值,求一棵生成树,满足 A/B 的值最大
其中,A = 生成树中任选的一条边所连接的两个点的权值和,B = 生成树总长 - 你选中的边的长度

思路:
为满足 A/B 最大,则必须使得 A 尽量大 ,B 尽量小。
假设选中的边已经确定,那么剩下的 n-2 条边肯定在最小生成树中(这是显然的)。那么,其实我们可以先生成一棵最小生成树,然后枚举他的边,将它暂时删除。
在一棵树中删除一条边,将形成两棵子树(这里把点也考虑上),为使重新构成生成树,我们必须在两棵子树之间重新构造一条边。为使 A 最大,我们只要两棵子树上分别寻在权值最大的点即可。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
const int maxn = 1005;
const double eps = 1e-6;

int n;
bool vis[maxn];

struct node {
    double x, y;
    int w;
} nodes[maxn];

struct edge {
    int from;
    int to;
    double dis;
    edge(int x = 0, int y = 0, int z = 0)
    {
        from = x;
        to = y;
        dis = z;
    }
    bool operator<(const edge& a) const
    {
        return dis > a.dis + eps;
    }
} edges[maxn][maxn];

vector<int> graph[maxn];
priority_queue<edge> que;

void init()
{
    while (!que.empty())
        que.pop();
    for (int i = 0; i <= n; i++)
        graph[i].clear();
    memset(vis, false, sizeof vis);
}

double cal(node& a, node& b)
{
    return sqrt((double)((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
}

double getSum(int cur, int pre, double sum)
{
    sum = max(sum, (double)(nodes[cur].w));
    int sz = graph[cur].size();
    for (int i = 0; i < sz; i++) {
        if (graph[cur][i] != pre)
            sum = max(sum, getSum(graph[cur][i], cur, sum));
    }
    return sum;
}

double pri_prime(int st)
{
    edge tmp;
    int v;
    double ans = 0;
    for (int i = 1; i <= n; i++)
        que.push(edges[st][i]);
    vis[st] = true;
    for (int i = 0; i < n - 1; i++) {
        do {
            tmp = que.top();
            que.pop();
        } while (vis[tmp.to]);
        v = tmp.to;
        vis[v] = true;
        ans += tmp.dis;
        graph[tmp.from].push_back(tmp.to);
        graph[tmp.to].push_back(tmp.from);
        for (int i = 1; i <= n; i++)
            if (!vis[i]) {
                tmp.from = v;
                tmp.to = i;
                tmp.dis = edges[v][i].dis;
                que.push(tmp);
            }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T;
    double sum;
    cin >> T;
    while (T--) {
        cin >> n;
        init();
        for (int i = 1; i <= n; i++)
            cin >> nodes[i].x >> nodes[i].y >> nodes[i].w;
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= n; j++) {
                edges[i][j].from = i;
                edges[i][j].to = j;
                edges[j][i].from = j;
                edges[j][i].to = i;
                edges[j][i].dis = edges[i][j].dis = cal(nodes[i], nodes[j]);
            }
        double final_len = pri_prime(1), ans = 0;
        for (int i = 1; i <= n; i++) {
            int sz = graph[i].size();
            for (int j = 0; j < sz; j++) {
                int v = graph[i][j];
                sum = getSum(v, i, 0) + getSum(i, v, 0);
                ans = max(ans, sum / (final_len - edges[i][v].dis));
            }
        }
        printf("%.2f\n", ans);
    }
    return 0;
}