最小生成树

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 。
    (这里我不细讲这些)

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

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

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

博弈

SHU 418 丢史蒂芬妮

Posted on

史蒂芬妮,空,白都是no game no life 里的人物,正值这个月15号剧场版即将上映,看得出来,出题人也是同道中人

这是一道勉强算得上博弈的博弈题。因为很那个……有点无法描述

题意:
给你一个 n × m 的棋盘,每次都只能向右,向下,向右下走质数个位置,哪个人先没路走哪个就算输。

思路:
为什么只能是勉强算得上是博弈,整个局势从最开始就是确定的,先手的空只能走一步,要么必赢,要么必输。嘛~ 这倒是很像空白风格的游戏。
我对每个格子从左上向右下判断,如果我能在之前的格子找到任意一个必输的局势,那么我当前位置必赢。由此不断往下递推即可。

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 505;
int Np[MAXN];
bool win[MAXN][MAXN];
vector<int> pr;

bool check(int x, int y)
{
    int l = max(x - 1, y - 1);
    bool res = false;
    for (int i = 0; !res && pr[i] <= l; i++) {
        if (x > pr[i])
            res |= (!win[x - pr[i]][y]);
        if (y > pr[i])
            res |= (!win[x][y - pr[i]]);
        if (x > pr[i] && y > pr[i])
            res |= (!win[x - pr[i]][y - pr[i]]);
    }
    return res;
}

void init()
{
    for (int i = 2; i < MAXN; i++) {
        if (!Np[i])
            pr.push_back(i);
        for (int j = 0; j < (int)pr.size(); j++) {
            int t = pr[j] * i;
            if (t >= MAXN)
                break;
            Np[t] = true;
            if (i % pr[j] == 0)
                break;
        }
    }
    for (int i = 1; i <= 500; i++)
        for (int j = 1; j <= 500; j++)
            win[i][j] = check(i, j);
}

int main()
{
    init();
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        printf("%s\n", win[n][m] ? "Sora" : "Shiro");
    }
    return 0;
}
Maths

SPOJ 104 Highways

Posted on

早上在学最小生成树计数。
最小生成树算法基于 Matrix-Tree 定理,Matrix-Tree定理是被广泛应用与求生成树计数中。
其具体流程为构造基尔霍夫矩阵,再对其求 n-1 阶行列式即可。

  • 基尔霍夫矩阵 为 其度数矩阵D[G] - 邻接矩阵A[G]
  • 度数矩阵D[G] 满足,当 i≠ j 时,dij=0;当i=j时,dij等于vi的度数。
  • 邻接矩阵A[G] 满足,如果vi、vj之间有边直接相连,则aij=1,否则为0。

不得不说SPOJ的数据之强,一个小问题找了我大半天才找着,SPOJ倒是我想做验证模板的不二之选。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define ll long long

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 105;

ll c[maxn][maxn];
ll degree[maxn];

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

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

int main()
{
    int T, u, v, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        memset(c, 0, sizeof c);
        memset(degree, 0, sizeof degree);
        while (m--) {
            scan_d(u);
            scan_d(v);
            c[u][v] = c[v][u] = -1;
            degree[u]++, degree[v]++;
        }
        for (int i = 1; i <= n; i++)
            c[i][i] = degree[i]; //因为不存在自环呀
        printf("%lld\n", getDet(c, n - 1));
    }
    return 0;
}