题目描述
一些公司会通过购买其他公司的部分股份以达到控制这些公司的目的。
一般来说,如果能够满足以下条件中的至少一项,则公司 $A$ 将会控制公司 $B$:
- 公司 $A$ = 公司 $B$
- 公司 $A$ 持有公司 $B$ 超过 $50\%$ 的股份
- 公司 $A$ 控制着 $K$ 个公司,这些公司表示为 $C1,C2,…,CK$,公司 $Ci$ 持有的公司 $B$ 的股份为 $Xi\%$,$X1+....+XK>50$
注意:
- 控股关系具有传递性,即如果公司 $A$ 控股公司 $B$,公司 $B$ 控股公司 $C$,那么公司 $A$ 控股公司 $C$。
- 数据保证控股关系不存在环。
给定一个三元组列表,列表中的每个三元组 $(i,j,p)$ 表示公司 $i$ 持有公司 $j$ 的 $p%$ 的股份。
我们用数对 $(h,s)$ 来表示公司 $h$ 控制着公司 $s$。
现在,请你找到并输出所有成立的数对 $(h,s)$。
输入格式
第一行包含整数 $N$,表示三元组列表中三元组的数量。
接下来 $N$ 行,每行包含三个整数 $i,j,p$,意义如上所述。
输出格式
每行包含两个整数 $h,s$,表示公司 $h$ 控制着公司 $s$。
输出所有满足条件的数对。
输出时,按第一个数升序排序输出,第一个数相同时,按第二个数升序排序输出。
另外,一个公司控制着自己,这种关系不需要输出。
数据范围
公司总数量不会超过 $100$
$1≤i,j,p≤100$
$1≤N≤2600$
输入样例
3
1 2 80
2 3 80
3 1 20
输出样例
1 2
1 3
2 3
DFS
我:不会的 DFS
这题很绕,真的很绕,其实理清楚了还是很清晰的。
这题有点像 传递闭包(y 总说)。
首先公司 $A$ 可以 直接 或 间接 控制公司 $B$ ,那么我们可以直接转化为公司 $A$ 控制公司 $B$,以权重 $W$ 来表示。
假设公司 $A$ 占股公司 $B$ 的 $X\%$ 的股份,若公司 $i$ 控制公司 $A$(公司 $A$ 也算控制公司 $A$),则公司 $i$ 应加上公司 $A$ 占股公司 $B$ 的 $X\%$ 的股份,由此引发的公司 $i$ 可能存在控制 $B$,如果公司 $i$ 已控制公司 $B$,则不做处理,因为之前一定处理过,否则进行下一步处理,公司 $i$ 控制公司 $B$,则公司 $i$ 应累加公司 $B$ 所占有其它公司的股份,其次控制公司 $i$ 的其它公司也应控制公司 $B$,需进行递归处理,然后由于第一步的累加公司 $B$ 所占有的其它公司股份,由此引发公司 $i$ 可能存在控制其它之前没有控制的公司,需进行递归处理。
其实这就是整个代码的思路,只是稍微理一理,至少不晕了。
C++ 代码
#include <iostream>
using namespace std;
const int N = 110;
int m, n = 100;
int w[N][N];
bool g[N][N];
void dfs(int x, int y)
{
if (g[x][y]) {
return ;
}
g[x][y] = true;
for (int i = 1; i <= n; ++i) {
w[x][i] += w[y][i];
}
for (int i = 1; i <= n; ++i) {
if (g[i][x]) {
dfs(i, y);
}
}
for (int i = 1; i <= n; ++i) {
if (w[x][i] > 50) {
dfs(x, i);
}
}
}
int main()
{
cin >> m;
for (int i = 1; i <= n; ++i) { // 公司 A = 公司 A
g[i][i] = true;
}
while (m--) {
int a, b, c;
cin >> a >> b >> c;
for (int i = 1; i <= n; ++i) {
if (g[i][a]) { // 公司 A 控制 公司 A
w[i][b] += c;
if (w[i][b] > 50) {
dfs(i, b);
}
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i != j && g[i][j]) {
cout << i << ' ' << j << endl;
}
}
}
return 0;
}