水晶铭刻之旅
时间限制：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)(109+7)取模。
【名词解释】
- 回路：回路 指沿传送门方向行走，最终回到起点的路径，可重复经过同一水晶或传送门。
- 铭刻方案：方案 指一系列回路操作，使得每块水晶至少在次回路中出现过一次。
输入描述
- 第一行输入整数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)(109+7)取模后的结果。
示例 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 = 31+2=3，方案数1 × 1 = 1 1 \times 1 = 11×1=1。
示例 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≤105
- 0 ≤ w i ≤ 10 9 0 \le w_i \le 10^90≤wi≤109
- 0 ≤ m ≤ 3 × 10 5 0 \le m \le 3 \times 10^50≤m≤3×105
- 1 ≤ 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^9+7109+7取模）。
- 遍历所有 SCC，将每个 SCC 的
- 输出：输出总消耗
sum和方案数ways。
3. 复杂度分析
- 时间复杂度：Tarjan 算法需要遍历所有节点和边一次，时间复杂度为O ( n + m ) O(n+m)O(n+m)。n ≤ 10 5 n \le 10^5n≤105，m ≤ 3 × 10 5 m \le 3 \times 10^5m≤3×105，完全可行。
- 空间复杂度：需要存储邻接表、
dfn、low、栈、SCC 信息等，空间复杂度为O ( n + m ) O(n+m)O(n+m)，满足 256M 限制。
总结
利用强连通分量将图缩点，每个 SCC 内部可以通过一次回路铭刻完全覆盖，且选择其中魔力最小的节点作为起点即可使该分量消耗最小。各 SCC 相互独立，总消耗为各分量最小魔力之和，方案数为各分量最小魔力节点个数的乘积。Tarjan 算法在线性时间内求出所有 SCC 并统计信息，整体思路清晰且高效。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=200000+10;constll M=1000000+10;constll mod=1000000007;constll INF=1e9;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 i=head[u];i!=0;i=nxt[i]){ll v=to[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 x=stk[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(x==u)break;}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(ll i=1;i<=n;i++){cin>>cost[i];}cin>>m;for(ll i=1;i<=m;i++){ll u,v;cin>>u>>v;addEdge(u,v);}for(ll i=1;i<=n;i++){if(dfn[i]==0){tarjan(i);}}ll sum=0;ll ways=1;for(ll i=1;i<=sccCnt;i++){sum+=minCost[i];ways=ways*minCnt[i]%mod;}cout<<sum<<" "<<ways;return0;}