题解 CF427C 【Checkposts】
VenusM1nT
2020-11-26 21:37:21
这波啊，这波是绿题上紫。
观察到是单向图，直接大力缩点，每个点的贡献就是点内权值最小的那个，加起来就得到了第一问的答案。记录一下每个点里有多少个贡献最小的，乘法原理乘起来一搞就出来了。
```cpp
#include<bits/stdc++.h>
#define N 100000
#define reg register
#define inl inline
using namespace std;
const int Mod=1e9+7;
int n,m,a[N+5],dfn[N+5],low[N+5],idx,bel[N+5],tot,siz[N+5],minx[N+5];
bool ins[N+5];
vector <int> g[N+5];
stack <int> s;
void Tarjan(reg int u)
{
dfn[u]=low[u]=++idx;
s.push(u);
ins[u]=1;
for(auto v : g[u])
{
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
reg int v=0;
tot++;
while(u!=v)
{
v=s.top();
s.pop();
bel[v]=tot;
ins[v]=0;
}
}
}
int main()
{
scanf("%d",&n);
for(reg int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for(reg int i=1;i<=m;i++)
{
reg int x,y;
scanf("%d %d",&x,&y);
g[x].push_back(y);
}
for(reg int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i);
memset(minx,60,sizeof(minx));
for(reg int i=1;i<=n;i++) minx[bel[i]]=min(minx[bel[i]],a[i]);
reg long long ans=0,Ans=1;
for(reg int i=1;i<=n;i++) if(minx[bel[i]]==a[i]) siz[bel[i]]++;
for(reg int i=1;i<=tot;i++) ans=ans+minx[i],Ans=Ans*1ll*siz[i]%Mod;
printf("%lld\n%lld\n",ans,Ans);
return 0;
}
```