水晶铭刻之旅时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述在远古魔法世界中有n nn块蕴含强大力量的魔法水晶第i ii块水晶的激活需要消耗魔力w i w_iwi​。这些水晶之间由m mm条单向传送门相连第j jj条传送门可将咒术师从水晶x j x_jxj​传送到水晶y j y_jyj​。咒术师掌握了回路铭刻术若他在某块水晶u uu处开启铭刻并沿着传送门行进最终能回到u uu那么经过的所有水晶都可一次性被铭刻仅需消耗起点水晶的激活魔力w u w_uwu​咒术师可多次从任意水晶发起回路直至所有水晶均被铭刻。请帮助咒术师在完成全部水晶铭刻的前提下将总消耗魔力最小化若存在多种消耗相同的最优铭刻方案计算方案总数并对( 10 9 7 ) (10^9 7)(1097)取模。【名词解释】回路回路 指沿传送门方向行走最终回到起点的路径可重复经过同一水晶或传送门。铭刻方案方案 指一系列回路操作使得每块水晶至少在次回路中出现过一次。输入描述第一行输入整数n ( 1 ≤ n ≤ 10 5 ) n\ (1 \le n \le 10^5)n(1≤n≤105)表示水晶数量第二行输入n nn个整数w 1 , w 2 , … , w n ( 0 ≤ w i ≤ 10 9 ) w_1, w_2, \dots, w_n\ (0 \le w_i \le 10^9)w1​,w2​,…,wn​(0≤wi​≤109)依次表示每块水晶的激活魔力第三行输入整数m ( 0 ≤ m ≤ 3 × 10 5 ) m\ (0 \le m \le 3 \times 10^5)m(0≤m≤3×105)表示传送门数量接下来m mm行每行输入两个整数x j , y j ( 1 ≤ x j , y j ≤ n ) x_j, y_j\ (1 \le x_j, y_j \le n)xj​,yj​(1≤xj​,yj​≤n)表示存在一条从水晶x j x_jxj​指向水晶y j y_jyj​的单向传送门。输出描述输出一行包含两个整数所需的最小总消耗魔力在该最小消耗下的可行铭刻方案数对( 10 9 7 ) (10^9 7)(1097)取模后的结果。示例 1输入3 1 2 3 3 1 2 2 3 3 2输出3 1说明示例中水晶{ 2 , 3 } \{2,3\}{2,3}构成回路可选起点魔力为min ⁡ ( 2 , 3 ) 2 \min(2,3) 2min(2,3)2水晶1 11独立付费1 11。总魔力1 2 3 1 2 3123方案数1 × 1 1 1 \times 1 11×11。示例 2输入3 10 20 10 4 1 2 1 3 3 1 2 1输出10 2说明示例中所有水晶互联可形成回路回路中最小激活魔力为10 1010可选水晶1 11或3 33故方案数为2 22。数据范围1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤1050 ≤ w i ≤ 10 9 0 \le w_i \le 10^90≤wi​≤1090 ≤ m ≤ 3 × 10 5 0 \le m \le 3 \times 10^50≤m≤3×1051 ≤ x j , y j ≤ n 1 \le x_j, y_j \le n1≤xj​,yj​≤n解题思路本题是强连通分量缩点 贪心计数的经典问题。给定一张有向图每个节点有一个激活魔力值一次“回路铭刻”可以从某个节点出发沿着有向边行走并最终回到起点路径上经过的所有节点均可被一次性铭刻总消耗仅为起点节点的激活魔力。要求用若干次回路铭刻覆盖所有节点最小化总消耗并统计达到最小消耗的方案数。1. 问题等价转化强连通分量内部可一次覆盖在有向图中若若干节点构成一个强连通分量SCC则从其中任意一个节点出发都可以沿着有向边遍历该分量内的所有节点并回到起点允许重复经过节点和边。因此一个强连通分量内的所有节点可以通过一次回路铭刻全部覆盖且这次铭刻的消耗仅由所选起点的魔力值决定。不同强连通分量相互独立缩点后SCC之间不存在回路因此每个SCC必须至少发起一次回路铭刻。不同SCC的回路选择互不影响总消耗为各SCC最小消耗之和方案数为各SCC方案数的乘积。单个SCC的最优选择对于每个SCC为了使消耗最小应选择该SCC内激活魔力最小的节点作为起点。若存在多个节点具有相同的最小魔力值则任选其一作为起点均可达到最优因此该SCC的方案数等于最小魔力值节点的个数。2. 算法实现建图读入节点数n nn、每个节点的魔力值w i w_iwi​、边数m mm以及m mm条有向边使用链式前向星存储。Tarjan 求强连通分量使用dfn和low数组进行深度优先搜索维护一个栈stk记录当前搜索路径上的节点。当dfn[u] low[u]时说明找到了一个强连通分量从栈中弹出节点直到u uu为这些节点分配同一个 SCC 编号。在弹出节点的过程中统计该 SCC 内的最小魔力值minCost以及达到该最小值的节点个数minCnt。统计答案遍历所有 SCC将每个 SCC 的minCost累加到总消耗sum中。将每个 SCC 的minCnt累乘到方案数ways中对10 9 7 10^971097取模。输出输出总消耗sum和方案数ways。3. 复杂度分析时间复杂度Tarjan 算法需要遍历所有节点和边一次时间复杂度为O ( n m ) O(nm)O(nm)。n ≤ 10 5 n \le 10^5n≤105m ≤ 3 × 10 5 m \le 3 \times 10^5m≤3×105完全可行。空间复杂度需要存储邻接表、dfn、low、栈、SCC 信息等空间复杂度为O ( n m ) O(nm)O(nm)满足 256M 限制。总结利用强连通分量将图缩点每个 SCC 内部可以通过一次回路铭刻完全覆盖且选择其中魔力最小的节点作为起点即可使该分量消耗最小。各 SCC 相互独立总消耗为各分量最小魔力之和方案数为各分量最小魔力节点个数的乘积。Tarjan 算法在线性时间内求出所有 SCC 并统计信息整体思路清晰且高效。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N20000010;constll M100000010;constll mod1000000007;constll INF1e9;ll head[N],to[M],nxt[M],idx;ll cost[N],dfn[N],low[N],stk[N],sccId[N];ll minCost[N],minCnt[N];boolinStk[N];ll n,m,timerCnt,top,sccCnt;voidaddEdge(ll u,ll v){to[idx]v;nxt[idx]head[u];head[u]idx;}voidtarjan(ll u){dfn[u]low[u]timerCnt;stk[top]u;inStk[u]true;for(ll ihead[u];i!0;inxt[i]){ll vto[i];if(dfn[v]0){tarjan(v);low[u]min(low[u],low[v]);}elseif(inStk[v]){low[u]min(low[u],dfn[v]);}}if(dfn[u]low[u]){sccCnt;minCost[sccCnt]INF;minCnt[sccCnt]0;while(true){ll xstk[top--];inStk[x]false;sccId[x]sccCnt;if(cost[x]minCost[sccCnt]){minCost[sccCnt]cost[x];minCnt[sccCnt]1;}elseif(cost[x]minCost[sccCnt]){minCnt[sccCnt];}if(xu)break;}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinn;for(ll i1;in;i){cincost[i];}cinm;for(ll i1;im;i){ll u,v;cinuv;addEdge(u,v);}for(ll i1;in;i){if(dfn[i]0){tarjan(i);}}ll sum0;ll ways1;for(ll i1;isccCnt;i){summinCost[i];waysways*minCnt[i]%mod;}coutsum ways;return0;}