题意
题目链接
sol
非常妙的一道题
设(inder[i])表示(i)号节点的度数
首先如果是个dag的话,可以考虑在每个点的入边中选一条边作为树形图上的边,这样(ans = prod_{i > 1} inder[i])
如果加入一条边的话,算答案的时候可能会把一些环的贡献也算进去(比如样例中(2 – 4 – 3))这个环
考虑减去环上的贡献,注意形成的环不止一个,准确的来说,如果加入了(x -> y)这条边,那么在原图中所有(y -> x)的路径都应该计算贡献
其中一条路径的贡献为(frac{ans}{s in (y -> x) inder[s]})
dp一遍求出所有贡献即可
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10, mod = 1e9 + 7; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, x, y, inder[maxn], inv[maxn], t[maxn], f[maxn]; vector<int> v[maxn]; void add(int &x, int y) { if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y); } int mul(int x, int y) { return 1ll * x * y % mod; } void topsort() { queue<int> q; for(int i = 1; i <= n; i++) if(!inder[i]) q.push(i); while(!q.empty()) { int p = q.front(); q.pop(); f[p] = mul(f[p], inv[t[p]]); for(int i = 0; i < v[p].size(); i++) { int to = v[p][i]; add(f[to], f[p]); if(!(--inder[to])) q.push(to); } } } int main() { n = read(); m = read(); x = read(); y = read(); inv[1] = 1; for(int i = 2; i <= m + 1; i++) inv[i] = mul((mod - mod / i), inv[mod % i]); for(int i = 1; i <= m; i++) { int x = read(), y = read(); v[x].push_back(y); inder[y]++; } int ans = 1; inder[y]++; for(int i = 2; i <= n; i++) ans = mul(ans, inder[i]); if(y == 1) {cout << ans; return 0;} memcpy(t, inder, sizeof(inder)); inder[y]--; f[y] = ans; topsort(); cout << (ans - f[x] + mod) % mod; return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/606140.html