UVA - 10766 Organising the Organisation
题意：
给你 n个点，m条边，以及一个k, m条边代表这m对点不能相连，k代表根节点。求有多少生成树。
题解：
1.注意是补图
2.生成树计数
请点击: 基尔霍夫矩阵树定理
无向图的基尔霍夫矩阵: 对角线上表示每个点的度数,若ij之间有边则矩阵ij处为-1
无向图的生成树的数目为: 任意一个n-1阶主子式的行列式的绝对值.
Cayley公式：完全图Kn有n^(n-2)颗生成树。
3.仔细思考一下，生成树的数目和根节点没有关系，所以与k无关
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 60 最后
以上就是孤独水壶最近收集整理的关于UVA - 10766 Organising the Organisation (生成树计数-补图） 基尔霍夫矩阵的全部内容，更多相关UVA内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复