UVa 10766 Organising the Organisation (生成树计数)
The 生成 UVa 计数
2023-09-11 14:17:18 时间
题意:给定一个公司的人数,然后还有一个boss,然后再给定一些人,他们不能成为直属上下级关系,问你有多少种安排方式(树)。
析:就是一个生成树计数,由于有些人不能成为上下级关系,也就是说他们之间没有边,没说的就是有边,用Matrix-Tree定理,很容易就能得到答案,注意题目给定的可能有重复的。
对于基尔霍夫矩阵,就是度数矩阵,减去邻接矩阵,一处理就OK了。
代码如下:
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string> #include <cstdlib> #include <cmath> #include <iostream> #include <cstring> #include <set> #include <queue> #include <algorithm> #include <vector> #include <map> #include <cctype> #include <cmath> #include <stack> #include <sstream> #include <bitset> #define debug() puts("++++"); #define gcd(a, b) __gcd(a, b) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define freopenr freopen("in.txt", "r", stdin) #define freopenw freopen("out.txt", "w", stdout) using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> P; const int INF = 0x3f3f3f3f; const LL LNF = 1e16; const double inf = 0x3f3f3f3f3f3f; const double PI = acos(-1.0); const double eps = 1e-8; const int maxn = 100 + 50; const int mod = 500500; const int dr[] = {-1, 0, 1, 0}; const int dc[] = {0, 1, 0, -1}; const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"}; int n, m; const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; inline bool is_in(int r, int c){ return r > 0 && r <= n && c > 0 && c <= m; } LL a[maxn][maxn]; int in[maxn]; LL solve(){ LL ans = 1; for(int i = 1; i < n; ++i){ for(int j = 1+i; 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] -= t * a[j][k]; for(int k = i; k < n; ++k) swap(a[i][k], a[j][k]); } if(a[i][i] == 0) return 0; ans *= a[i][i]; } return abs(ans); } int main(){ int k; while(scanf("%d %d %d", &n, &m, &k) == 3){ for(int i = 1; i <= n; ++i){ for(int j = i+1; j <= n; ++j) a[i][j] = a[j][i] = -1; in[i] = n - 1; } for(int i = 0; i < m; ++i){ int u, v; scanf("%d %d", &u, &v); if(a[u][v] == -1) --in[v], --in[u]; a[u][v] = a[v][u] = 0; } for(int i = 1; i <= n; ++i) a[i][i] = in[i]; LL ans = solve(); printf("%lld\n", ans); } return 0; }
相关文章
- Understanding the Objective-C Runtime
- 新建maven指定jdk版本-eclipse新建maven项目报错The superclass "javax.servlet.http.HttpServlet" was not found on the Java Build Path的解决方案
- HTTP Status 500 - The absolute uri: http://java.sun.com/jsp/jstl/core cannot be resolved in either web.xml or the jar files deployed with this application
- 【异常】[ERROR] The cloud assistant is not installed on the ECS, or the cloud assistant is unavailable. cloudassistant is uninstall
- [React] Render Elements Outside the Current React Tree using Portals in React 16
- [React] React Fundamentals: The Render Method
- ASP.NET MVC - The view must derive from WebViewPage, or WebViewPage<TModel>
- MySQL提示:The server quit without updating PID file问题的解决办法
- [Debug] How to Debug a NestJs Backend using the Chrome Dev Tools
- [Angular2 Router] Optional Route Query Parameters - The queryParams Directive and the Query Parameters Observable
- [Angular2 Router] Programmatic Router Navigation via the Router API - Relative And Absolute Router Navigation
- [Javascript + rxjs] Using the map method with Observable
- 【Codeforces Round #452 (Div. 2) C】 Dividing the numbers
- 【Uva 11080】Place the Guards
- Error Domain=NSCocoaErrorDomain Code=518 “The file couldn’t be saved because the specified URL type
- 成功解决MSB8020 The build tools for v141 (Platform Toolset = ‘v141‘) cannot be found. To build using the
- 成功解决tensorboard调用events.out.tfevents文件得到网址出现No dashboards are active for the current data set问题
- NLP:LSTM之父眼中的深度学习十年简史《The 2010s: Our Decade of Deep Learning / Outlook on the 2020s》的参考文献
- 已解决The above exception was the direct cause of the following exception:
- EnvironmentNotWritableError: The current user does not have write permissions to the targe...
- RuntimeError: Input type (torch.cuda.FloatTensor) and weight type (torch.FloatTensor) should be the
- The size of tensor a (4) must match the size of tensor b (3) at non-singleton dimension 0
- 3GPP TS 29244-g30 中英文对照 | 5.5.3F-TEID allocation in the UP function
- java.lang.IllegalStateException: The specified child already has a parent. You must call removeView() on the child's parent first.
- Warning:detected "cgroupfs" as the Docker cgroup driver. The recommended driver is "systemd".
- 编译webrtc报错:ERROR: The installation of the Chrome OS default fonts failed.
- ERROR 1290 (HY000): The MySQL server is running with the --secure-file-priv option so it cannot ···
- 存在隐患 : 3 racks are required for the erasure coding policies: RS-6-3-1024k. The number of racks is on
- git push报错 fatal: The current branch master has no upstream branch. To push the current
- Sentinel采用SphO方式定义资源,报错:The order of entry exit can‘t be paired with the order of entry
- 【异常】前端ERR! stack Error: Can‘t find Python executable “python“, you can set the PYTHON env variable.
- 【异常】FlinkException: The module flink-runtime-web could not be found in the class path