题意是给你一些公司的股份控制关系， 如果公司A控股公司B的比例超过50%， 那么公司A就控制了B公司， 在公司A控制的所有子公司中，假设子公司控制另外一个公司的股权和超过50%那么公司A间接控制这个公司， 现在给你一些公司的控制关系， 求出所有的控制公司对，感觉蛮好的一道题， 刚开始想用floyd来解决， 后来发现这种方法并不是很好， 最后参考了下题解中的dfs做法， 大体思路就是假设公司i控制公司j， 那么就用这个信息去更新公司i不直接控制的公司， 代码如下：
/* ID: m1500293 LANG: C++ PROG: concom */ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int con1[105][105], con2[105][105]; int n, tp; void dfs(int i, int j) { for(int k=1; k<=tp; k++) { if(i!=k && con2[i][k]<=50) { con2[i][k] += con1[j][k]; if(con2[i][k]>50) dfs(i, k); } } } int main() { freopen("concom.in", "r", stdin); freopen("concom.out", "w", stdout); scanf("%d", &n); memset(con1, 0, sizeof(con1)); tp = 0; for(int i=0; i<n; i++) { int u, v, c; scanf("%d%d%d", &u, &v, &c); con1[u][v] = c; tp = max(tp, max(u, v)); } memcpy(con2, con1, sizeof(con1)); for(int i=1; i<=tp; i++) for(int j=1; j<=tp; j++) if(con2[i][j] > 50) dfs(i, j); for(int i=1; i<=tp; i++) for(int j=1; j<=tp; j++) if(i!=j && con2[i][j] > 50) printf("%d %d\n", i, j); return 0; }
原文：http://www.cnblogs.com/xingxing1024/p/5076672.html