思路
两层循环+dfs搜完所有情况(代码见下方)
如果A控制B,dfs(A,B),dfs内部根据性质三,把B持有的其他公司的股份(比如X)加到A公司里,如果w[A][X]>50,继续dfs(A,X)
w[A][B]表示A公司拥有B公司股份的值
g[A][B]表示A公司是否控制B公司
是否全搜过
如果公司A实际控制公司X
1 公司A直接控制公司X,即w[A][X] > 50, (main函数里两层循环搜到过)
2 公司A通过控制公司B,C,D…控制公司X,公司BCD等公司在dfs中搜索过,且dfs中BCD等公司拥有公司X的股份也加到w[A][X]中,DFS搜索中一旦W[A][X]>50,直接dfs(A,X), 所以A间接控制X公司的情况也搜过。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n = 100, m;
int w[N][N];
bool g[N][N];
void dfs(int a, int b)
{
// if (!g[a][b]) return; dfs之前已经判断过了g[a][b] != 1
g[a][b] = true; // 标记a控制b
for (int x = 1; x <= n; x ++) // a控制了b, 由性质三,b持有的其他公司股份加到a里
if (b != x && !g[a][x]) // 如果a已经控制了x,剪枝
{
w[a][x] += w[b][x]; // 加都可以加
if (w[a][x] > 50) // 控股过50开搜
dfs(a, x);
}
}
int main()
{
cin >> m;
for (int i = 1; i <= n; i ++) g[i][i] = true;
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
w[a][b] += c;
}
for (int i = 1; i <= n; i ++) // 两层循环+dfs
for (int j = 1; j <= n; j ++)
if (j != i && w[i][j] > 50 && !g[i][j]) // 控股过50且没标记过, 开搜
dfs(i, j);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
if (i != j && g[i][j])
printf("%d %d\n", i, j);
return 0;
}