P1475 控制公司 Controlling Companies网页链接P1475 控制公司 Controlling Companies题目描述有些公司是其他公司的部分拥有者因为他们获得了其他公司发行的股票的一部分。据说如果至少满足了以下三个条件之一公司A AA就可以控制公司B BB了公司A AA 公司B BB。公司A AA拥有大于50 % 50\%50%的公司B BB的股票。公司A AA控制K KKK ≥ 1 K \geq 1K≥1个公司记为C 1 , … , C K C_1, \ldots, C_KC1,…,CK每个公司C i C_iCi拥有x i % x_i\%xi%的公司B BB的股票并且x 1 … x K 50 % x_1 \ldots x_K \gt 50\%x1…xK50%。给你一个表每行包括三个数i , j , p i,j,pi,j,p表明公司i ii享有公司j jj的p % p\%p%的股票。计算所有的数对( h , s ) (h,s)(h,s)表明公司h hh控制公司s ss。至多有100 100100个公司。输入格式第一行一个整数N NN表明表格的行数。接下来N NN行每行三个整数i , j , p i,j,pi,j,p表示i ii公司拥有j jj公司p % p\%p%的股份。输出格式输出零个或更多个的控制其他公司的公司。每行包括两个整数A , B A,BA,B表示A AA公司控制了B BB公司。将输出的数对以A AA为第一关键字B BB为第二关键字升序排列。请不要输出控制自己的公司即你输出的数对均要满足A ≠ B A \neq BAB。输入输出样例 #1输入 #13 1 2 80 2 3 80 3 1 20输出 #11 2 1 3 2 3说明/提示翻译来自NOCOWUSACO 2.3解题思路本题是带权重累加的传递闭包问题核心是利用控制关系的传递性若A控制B则B持有的所有股份都可被A支配用于判断A是否能控制更多公司。由于公司总数不超过100采用枚举起点DFS传播的方式即可高效求解。1. 问题核心分析控制关系的三条规则可归纳为自反性每个公司天然控制自己。直接控制直接持股超过50%即可控制。传递控制所有被当前公司控制的公司其持有的股份可累加若总和超过50%则可控制新的公司且该过程可多层传递。问题的关键在于控制新公司后需要将其持股纳入总份额可能触发更多控制关系因此需要迭代/递归传播直到没有新公司被控制为止。2. 算法设计枚举起点 DFS传播对每个公司作为控股股东单独计算它能控制的所有公司数据存储用二维数组a[i][j]存储公司 i 直接持有公司 j 的股份比例。状态初始化对每个起点 h初始化三个数组f[j]当前 h 可支配的 j 公司的总股份初始全为0。v[j]标记公司 j 是否已被纳入控制并贡献过股份避免重复计算。c[j]标记公司 j 是否被 h 控制。DFS 传播控制从起点 h 开始DFS默认 h 自己被控制因此直接处理它的持股。对当前处理的公司 k将其持有的所有股份累加到总持股数组f中。遍历所有公司若某公司的总持股f[j] 50且未被处理过说明 h 成功控制了 j标记c[j] true并递归DFS处理j将其持股也纳入总份额。结果收集DFS结束后所有c[j] true且j ≠ h的公司就是h控制的其他公司。3. 输出与复杂度按编号从小到大枚举起点再从小到大枚举受控公司输出结果天然满足按A升序、再按B升序的要求。时间复杂度设最大公司编号为 m≤100总复杂度为O ( m 3 ) O(m^3)O(m3)运算量约百万级完全适配1秒时间限制。总结核心逻辑枚举每个公司作为起点通过DFS递归传播控制关系每控制一个新公司就将其持股累加到总份额中持续判断并扩展受控集合最终得到所有控制对。关键操作持股矩阵存储、总股份累加、DFS传递控制、访问标记防重复。效率保障公司规模极小暴力枚举DFS的方案简洁且不易出错运行开销极低。代码简要说明全局数组a[110][110]存储直接持股比例a[i][j]表示i持有j的股份百分比。f[110]记录当前起点公司可支配的目标公司总股份。v[110]标记公司是否已被处理过已贡献过持股。c[110]标记公司是否被当前起点控制。DFS函数若当前公司已访问则直接返回避免重复处理。标记为已访问后遍历所有公司将当前公司的持股累加到总持股数组。对每个公司若总持股超过50%标记为受控并递归处理该公司实现控制关系的传递。主函数逻辑读入持股数据同步维护最大公司编号n。外层枚举每个公司作为起点重置三个状态数组后启动DFS。内层遍历所有公司输出所有受控且不等于起点的公司对。输入输出使用scanf/printf保证读写效率适配题目数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n;ll a[110][110],f[110];boolv[110],c[110];voiddfs(ll k){if(v[k])return;v[k]true;for(ll i1;in;i){f[i]a[k][i];if(f[i]50){c[i]true;dfs(i);}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll i,j,x,y,z,t;scanf(%lld,t);for(i1;it;i){scanf(%lld%lld%lld,x,y,z);a[x][y]z;nmax(n,max(x,y));}for(i1;in;i){memset(v,0,sizeof(v));memset(c,0,sizeof(c));memset(f,0,sizeof(f));dfs(i);for(j1;jn;j)if(c[j]i!j)printf(%lld %lld\n,i,j);}return0;}
P1475 控制公司 Controlling Companies【洛谷算法习题】
P1475 控制公司 Controlling Companies网页链接P1475 控制公司 Controlling Companies题目描述有些公司是其他公司的部分拥有者因为他们获得了其他公司发行的股票的一部分。据说如果至少满足了以下三个条件之一公司A AA就可以控制公司B BB了公司A AA 公司B BB。公司A AA拥有大于50 % 50\%50%的公司B BB的股票。公司A AA控制K KKK ≥ 1 K \geq 1K≥1个公司记为C 1 , … , C K C_1, \ldots, C_KC1,…,CK每个公司C i C_iCi拥有x i % x_i\%xi%的公司B BB的股票并且x 1 … x K 50 % x_1 \ldots x_K \gt 50\%x1…xK50%。给你一个表每行包括三个数i , j , p i,j,pi,j,p表明公司i ii享有公司j jj的p % p\%p%的股票。计算所有的数对( h , s ) (h,s)(h,s)表明公司h hh控制公司s ss。至多有100 100100个公司。输入格式第一行一个整数N NN表明表格的行数。接下来N NN行每行三个整数i , j , p i,j,pi,j,p表示i ii公司拥有j jj公司p % p\%p%的股份。输出格式输出零个或更多个的控制其他公司的公司。每行包括两个整数A , B A,BA,B表示A AA公司控制了B BB公司。将输出的数对以A AA为第一关键字B BB为第二关键字升序排列。请不要输出控制自己的公司即你输出的数对均要满足A ≠ B A \neq BAB。输入输出样例 #1输入 #13 1 2 80 2 3 80 3 1 20输出 #11 2 1 3 2 3说明/提示翻译来自NOCOWUSACO 2.3解题思路本题是带权重累加的传递闭包问题核心是利用控制关系的传递性若A控制B则B持有的所有股份都可被A支配用于判断A是否能控制更多公司。由于公司总数不超过100采用枚举起点DFS传播的方式即可高效求解。1. 问题核心分析控制关系的三条规则可归纳为自反性每个公司天然控制自己。直接控制直接持股超过50%即可控制。传递控制所有被当前公司控制的公司其持有的股份可累加若总和超过50%则可控制新的公司且该过程可多层传递。问题的关键在于控制新公司后需要将其持股纳入总份额可能触发更多控制关系因此需要迭代/递归传播直到没有新公司被控制为止。2. 算法设计枚举起点 DFS传播对每个公司作为控股股东单独计算它能控制的所有公司数据存储用二维数组a[i][j]存储公司 i 直接持有公司 j 的股份比例。状态初始化对每个起点 h初始化三个数组f[j]当前 h 可支配的 j 公司的总股份初始全为0。v[j]标记公司 j 是否已被纳入控制并贡献过股份避免重复计算。c[j]标记公司 j 是否被 h 控制。DFS 传播控制从起点 h 开始DFS默认 h 自己被控制因此直接处理它的持股。对当前处理的公司 k将其持有的所有股份累加到总持股数组f中。遍历所有公司若某公司的总持股f[j] 50且未被处理过说明 h 成功控制了 j标记c[j] true并递归DFS处理j将其持股也纳入总份额。结果收集DFS结束后所有c[j] true且j ≠ h的公司就是h控制的其他公司。3. 输出与复杂度按编号从小到大枚举起点再从小到大枚举受控公司输出结果天然满足按A升序、再按B升序的要求。时间复杂度设最大公司编号为 m≤100总复杂度为O ( m 3 ) O(m^3)O(m3)运算量约百万级完全适配1秒时间限制。总结核心逻辑枚举每个公司作为起点通过DFS递归传播控制关系每控制一个新公司就将其持股累加到总份额中持续判断并扩展受控集合最终得到所有控制对。关键操作持股矩阵存储、总股份累加、DFS传递控制、访问标记防重复。效率保障公司规模极小暴力枚举DFS的方案简洁且不易出错运行开销极低。代码简要说明全局数组a[110][110]存储直接持股比例a[i][j]表示i持有j的股份百分比。f[110]记录当前起点公司可支配的目标公司总股份。v[110]标记公司是否已被处理过已贡献过持股。c[110]标记公司是否被当前起点控制。DFS函数若当前公司已访问则直接返回避免重复处理。标记为已访问后遍历所有公司将当前公司的持股累加到总持股数组。对每个公司若总持股超过50%标记为受控并递归处理该公司实现控制关系的传递。主函数逻辑读入持股数据同步维护最大公司编号n。外层枚举每个公司作为起点重置三个状态数组后启动DFS。内层遍历所有公司输出所有受控且不等于起点的公司对。输入输出使用scanf/printf保证读写效率适配题目数据规模。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n;ll a[110][110],f[110];boolv[110],c[110];voiddfs(ll k){if(v[k])return;v[k]true;for(ll i1;in;i){f[i]a[k][i];if(f[i]50){c[i]true;dfs(i);}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll i,j,x,y,z,t;scanf(%lld,t);for(i1;it;i){scanf(%lld%lld%lld,x,y,z);a[x][y]z;nmax(n,max(x,y));}for(i1;in;i){memset(v,0,sizeof(v));memset(c,0,sizeof(c));memset(f,0,sizeof(f));dfs(i);for(j1;jn;j)if(c[j]i!j)printf(%lld %lld\n,i,j);}return0;}
