首先一读完题，就觉得是拓扑排序，然而我基本上不会写拓扑（悲）
所以，爆搜！启动！
出乎意料的是竟然没有 TLE ，而是因为爆 unsigned long long WA 了两个点。光荣地得了 80pts！
解题思路
已经说过了，爆搜。
当然，是有技巧的。不然写着很累。
分数运算
题目要求输出分数，比较麻烦，所以我们先解决分数运算
首先，我们用 $p$ 和 $q$ 分别存一个分数的分子和分母。
然后实现约分，具体方法为直接模拟，上过小学的都会。最小公倍数可以用 STL 中的 __gcd 函数：
1
2
| int gcd = __gcd(p, q);
p /= gcd, q /= gcd;
|
然后是除法，根据小学学过的 $\frac{a}{b} / \frac{c}{d} = \frac{a}{b} * \frac{d}{c} = \frac{a * d}{b * c}$ 。又因为是分成若干份，所以一定是除以一个整数，也就是说 $d = 1$ 。所以我们只需要把分母 q 乘上要分成的份数，再约分就可以了。
1
2
3
| q *= e[x].size();
int gcd = __gcd(p, q);
p /= gcd, q /= gcd;
|
最后我们再来写最烦的加法。根据小学学过的分数的运算先通分，然后分子相加，最后约分，就好了，写起来还是比较麻烦的。
1
2
3
4
5
6
7
| int gcd = __gcd(qq, q);
int lcm = qq * q / gcd;
pp = pp * (lcm / qq) + p * (lcd / q);
qq = lcm;
gcd = __gcd(pp,qq);
pp /= gcd;
qq /= gcd;
|
爆搜
大部分人写的应该都是电风扇，但是我写了 bfs。
首先把几个起点全部加入队列，虽然题目写的是会几股水合成一股的，不太好写，但是根据乘法分配律（前面说过了，除以一个数可以当成乘以它的倒数）与加法结合律，我们可以证明每股分开来算，在最后加起来不会影响结果。
80pts code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N = 1e5 + 5;
struct Node
{
int x, p, q;
};
struct Point
{
int p, q;
} ans[N];
int n, m, cnt[N];
vector<int> e[N];
void bfs()
{
queue<Node> Q;
for (int i = 1; i <= n; i++)
{
if (cnt[i] == 0)
Q.push({i, 1, 1});
}
while (!Q.empty())
{
Node now = Q.front();
Q.pop();
int x = now.x, p = now.p, q = now.q;
if (e[x].size() == 0)
{
if (ans[x].p == 0 && ans[x].q == 0)
ans[x].p = p, ans[x].q = q;
else
{
int gcd = __gcd(ans[x].q, q);
int lcm = ans[x].q * q / gcd;
ans[x].p = ans[x].p * (lcm / ans[x].q) + p * (lcm / q);
ans[x].q = lcm;
gcd = __gcd(ans[x].p, ans[x].q);
ans[x].p /= gcd;
ans[x].q /= gcd;
}
continue;
}
q *= e[x].size();
int gcd = __gcd(p, q);
p /= gcd, q /= gcd;
for (auto i : e[x])
{
Q.push({i, p, q});
}
}
}
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int d;
cin >> d;
for (int j = 1; j <= d; j++)
{
int a;
cin >> a;
e[i].push_back(a);
cnt[a]++;
}
}
bfs();
for (int i = 1; i <= n; i++)
{
if (e[i].size() == 0)
{
int gcd = __gcd(ans[i].p, ans[i].q);
ans[i].p /= gcd;
ans[i].q /= gcd;
cout << ans[i].p << " " << ans[i].q << endl;
}
}
}
|
爆 unsigned long long WA 了两个点，要么开__128 要么用高精度。
AC code（__int128）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| #include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct Node
{
__int128 x, p, q;
};
struct Point
{
__int128 p, q;
} ans[N];
int n, m, cnt[N];
vector<int> e[N];
void bfs()
{
queue<Node> Q;
for (int i = 1; i <= n; i++)
{
if (cnt[i] == 0)
Q.push({i, 1, 1});
}
while (!Q.empty())
{
Node now = Q.front();
Q.pop();
__int128 x = now.x, p = now.p, q = now.q;
if (e[x].size() == 0)
{
if (ans[x].p == 0 && ans[x].q == 0)
ans[x].p = p, ans[x].q = q;
else
{
__int128 gcd = __gcd(ans[x].q, q);
__int128 lcm = ans[x].q * q / gcd;
ans[x].p = ans[x].p * (lcm / ans[x].q) + p * (lcm / q);
ans[x].q = lcm;
gcd = __gcd(ans[x].p, ans[x].q);
ans[x].p /= gcd;
ans[x].q /= gcd;
}
continue;
}
q *= e[x].size();
int gcd = __gcd(p, q);
p /= gcd, q /= gcd;
for (auto i : e[x])
{
Q.push({i, p, q});
}
}
}
void print(__int128 x)
{
if(x < 0)
{
putchar('-');
x = -x;
}
if(x > 9)
print(x / 10);
putchar(x % 10 + '0');
}
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
int d;
cin >> d;
for (int j = 1; j <= d; j++)
{
int a;
cin >> a;
e[i].push_back(a);
cnt[a]++;
}
}
bfs();
for (int i = 1; i <= n; i++)
{
if (e[i].size() == 0)
{
int gcd = __gcd(ans[i].p, ans[i].q);
ans[i].p /= gcd;
ans[i].q /= gcd;
print(ans[i].p);
cout << " ";
print(ans[i].q);
cout << endl;
}
}
}
|
hack 数据
虽然但是，爆搜时间复杂度是指数级的 （可能是 $O(nmd)$ ？） 的，本来只能拿 30 分但是数据太水居然放过了，只要让每个点的出边都是 5 条就可以轻松卡掉，hack 数据（数据由123456zmy）提供。
关于__int128
当时__int128是无法使用的，而现在__int128 在 NOI 系列赛和 CSP-J/S 等活动中已经解禁了。
尽管它不是 C++标准的一部分，但在某些编译器（如 GCC、G++）的64 位版本中得到了支持。根据 NOI 官网的文章：NOI Linux 2.0 发布，将于 9 月 1 日起正式启用！，该系统自 2021 年 9 月 1 日起作为 NOI 系列比赛和 CSP-J/S 等活动的标准环境使用。
根据 NOI Linux 2.0 的**“系统情况简表”**，系统为 64 位并且使用 G++9.3.0 作为 C++编译器。所以万能头文件及 __int128 全面解禁！！！
