SPOJ104 Highways,跨越数
跨越
2023-09-14 09:08:06 时间
高速公路(SPOJ104 Highways)
一个有n座城市的组成国家,城市1至n编号,当中一些城市之间能够修建快速公路。如今,须要有选择的修建一些快速公路。从而组成一个交通网络。你的任务是计算有多少种方案,使得随意两座城市之间恰好仅仅有一条路径?
数据规模:1≤n≤12。
生成树计数
算法步骤:
1、 构建拉普拉斯矩阵
Matrix[i][j] =
degree(i) , i==j
-1,i-j有边
0,其它情况
2、 去掉第r行,第r列(r随意)
3、 计算矩阵的行列式
#include <map> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int maxn = 105; const int maxm = 100005; const int INF = 1e9; int degree[maxn]; ll g[maxn][maxn]; int n, m; ll det(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]; } if(ret<0){ ret = -ret; } return ret; } void solve() { int u, v; memset(degree, 0, sizeof degree ); memset(g, 0, sizeof g ); scanf("%d%d", &n, &m); while(m--){ scanf("%d%d", &u, &v); u--,v--; g[u][v] = g[v][u] = -1; degree[u]++; degree[v]++; } for(int i=0; i<n; ++i){ g[i][i] = degree[i]; } printf("%lld\n", det(g, n)); } int main() { int t; scanf("%d", &t); while(t--){ solve(); } return 0; }
版权声明:本文博主原创文章。博客,未经同意不得转载。
相关文章
- 远程控制 Linux:实现跨越时空的管理(远程控制linux)
- Oracle SL150:领先技术,跨越世界(oraclesl150)
- 控制Linux Vim让你跨越权限之境(linuxvim权限)
- Linux:轻松跨越多个平台(linux跨平台)
- 跨越敏捷的那些坑
- Linux网络应聘指南:跨越面试关卡(linux网络面试题)
- 跨越Linux,助你轻松畅游IT世界(crosslinux)
- 如何跨越 Kubernetes 学习曲线
- 优化SQL Server迁移与优化:实现跨越技术边界的突破(sqlserver迁移和)
- Linux遥控器:掌控跨越计算的新世界(linux 遥控器)
- Oracle全局域名领航跨越地球的数据连接(oracle 全局域名)
- 1025MySQL跨越进化史的里程碑(1025mysql)
- 架构跨越未来Oracle企业版实例研究(oracle企业版实例)
- oracle云中心有望冲击多领域万达Oracle云大会推动云中心创新跨越多领域(oracle云大会 万达)
- Oracle数据库跨越数据管理的新界线(oracle。结束会话)
- 访问远程访问Redis主机跨越局域网的连接(redis 远程主机)