怎样申请免费网站,郑州郑东新区,网站搭建协议,wordpress 仿小米主题Description 在图论中#xff0c;树的定义是连通且无环的无向图。对于一棵有 nn 个节点且节点从 11 到 nn 编号的树#xff0c;它的 Prufer 序列是一个唯一的长为 n−2n−2 的标号序列。 Prufer 序列的构造方法#xff1a;每次删除树中标号最小的叶子节点#xff08;即度为… Description 在图论中树的定义是连通且无环的无向图。对于一棵有 nn 个节点且节点从 11 到 nn 编号的树它的 Prufer 序列是一个唯一的长为 n−2n−2 的标号序列。 Prufer 序列的构造方法每次删除树中标号最小的叶子节点即度为 11 的节点将该点的邻居加到当前 Prufer 序列的末尾直到只剩两个节点为止。 例子 给定一个 nn 个顶点从 11 到 nn 标号 mm 条边的无向图 GGGG 中无重边或自环。随机选择 GG 的一棵生成树计算他的 Prufer 序列的和 SS重复元素只算一次。 请计算随机变量 SS 的期望。注意GG 的生成树或某棵生成树的 Prufer 序列都可能不存在这种情况下我们认为随机变量 SS 的值为 00。 为了避免精度问题 算出实际的期望值乘以图 GG 的不同生成树的数目以后的值即可。 这个值可能很大请输出它对 10971097 取模以后的值。 Input 每个输入文件包含多组测试数据。输入文件的第一行是测试数据组数 TT (T≤10T≤10)。 对于每组测试数据第一行是两个整数 n,mn,m (3≤n≤100,0≤m≤(n−1)n23≤n≤100,0≤m≤(n−1)n2 分别是图的点数和边数接下来 mm 行每行包含两个整数 u,vu,v1≤u,v≤n1≤u,v≤nu≠vu≠v表示图中的一条边。 Output 输出 TT 行每行是对应的答案。 Sample Input
1
3 3
1 2
2 3
1 3 Sample Output
6 题目大意求所有生成树的prufer序列和prufer中有重复序列的只算一次
题解
这样的话对于每一颗生成树我们可以把所有的点全都加进去然后再减去叶子结点的和。
我们不可能找到所有的生成树然后一个一个的计算因此我们用矩阵树定理来做。
我们先计算图所有的点的和并且乘以生成树的数量把他们放在sum里。然后再把所有的叶子结点减去就好了
如果一个叶子节点出现在一颗子树里那么把这个点去掉仍然可一得到图的该生成树而如果这个点是内部节点就不行了。
注意如果这个叶子节点的度不为1那么要用这个叶子节点的度数乘以生成树的数量才是这个叶子节点对应生成树的个数。
sum - 去掉该节点生成树的数量*该节点的度*该节点的值。
最后得到的sum就是答案
代码 #includeiostream。
#includecmath
#include cstring
using namespace std;
#define zero(x)((x0? x:-x)1e-15)
#define int long long
int const MAXN 105;
const int mod 1e9 7;
int a[MAXN][MAXN];
int b[MAXN][MAXN];
int g[103][103];
int d[105];
int n, m;
int det(int a[MAXN][MAXN], int n){ int s0;for(int i0; in; i){ int ri; for(; rn; r) // error-prone if(a[r][i]) break; if(rn1) return 0; if(r!i){ s^1; for(int ji; jn; j) swap(a[i][j], a[r][j]); } for(int ji1; jn; j){ int xi, yj; for(; a[y][i]; ){ // print(a, n); int ta[y][i]/a[x][i]; if(t){ for(int ki; kn; k){ a[y][k] - t*a[x][k]%mod; a[y][k] % mod; } if(a[y][i]0) break; } swap(x, y); } if(x!i){ for(int ki; kn; k) swap(a[x][k], a[y][k]); s ^ 1; } } } int res1; for(int i0; in; i) res*a[i][i], res%mod; if(s){ res-res; }if(res 0) resmod; return res;
} void prep(int n,int x)
{for(int i 0;i n;i){for(int j 0;j n;j){a[i][j] (i j)?d[i]-g[i][x]:-g[i][j];}}if(x 1){for(int i 0;i n;i) a[x][i] a[i][x] 0;a[x][x] 1;}
}main()
{ int cas;scanf(%lld, cas);while (cas--) {memset(g,0,sizeof(g));memset(d,0,sizeof(d));memset(a,0,sizeof(a));memset(b,0,sizeof(b));scanf(%lld%lld, n,m);for(int i 0;i m;i){int u,v;scanf(%lld%lld,u,v);u--,v--;d[u];d[v];g[u][v] g[v][u] 1;}prep(n,-1);int sum det(a,n-1)*((1n)*n/2) % mod;for(int i 0;i n-1;i){prep(n,i);sum (sum - (i1)*d[i] % mod * det(a,n-1) % mod mod)%mod;//cout:sumendl;}prep(n,n-1);sum (sum - n*d[n-1] % mod * det(a,n-2) % mod mod)%mod;coutsumendl;}return 0;
}
