#include<bits/stdc++.h>
typedef long long LL;
typedef unsigned long long LLU;
const int inf=0x3f3f3f3f;
const int MAXN=100005;
const int mod=1000000007;
const int INF = 0x7fffffff ;
using namespace std;
struct edge
{
int to,next,fr;
};
edge e[30005],ne[30005];
int head[10005],dfn[10005],low[10005],col[10005],nhead[10005];
int a[10005],in[10005],vis[10005],sum[10005],w[10005];
int n,m,nn;
int cnt=0;
stack<int>s;
void add(int u,int v)
{
e[cnt].to=v;
e[cnt].fr=u;
e[cnt].next=head[u];
head[u]=cnt;
cnt++;
}
int ss=0;
void tarjan(int x)
{
ss++;
low[x]=dfn[x]=ss;
vis[x]=1;
s.push(x);
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(!dfn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(vis[v])
{
low[x]=min(low[x],dfn[v]);
}
}
if(dfn[x]==low[x])
{
int tmp;
while(tmp=s.top())
{
col[tmp]=x;
vis[tmp]=0;
s.pop();
if(x==tmp)break;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int u,v;
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>u>>v;
add(u,v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
{
int tmp=0,cnt=0;
for(int j=1;j<=n;j++)
{
if(col[j]==i)
{
if(tmp==0)
{
tmp=a[j]; cnt=1;
}
else
{
if(tmp>a[j])
{
cnt=1; tmp=a[j];
}
else if(tmp==a[j])
{
cnt++;
}
}
}
}
sum[i]=cnt;w[i]=tmp;
}
int x,y;
for(int i=1;i<=m;i++)
{
x=col[e[i].fr];y=col[e[i].to];
if(x!=y)
{
nn++;
ne[nn].fr=x;
ne[nn].to=y;
ne[nn].next=nhead[x];
nhead[x]=nn;
in[y]++;
}
}
int ans=0,ans1=1;
for(int i=1;i<=n;i++)
{
if(in[i]==0)
{
ans+=w[col[i]];
ans1*=sum[col[i]];
}
}
cout<<ans<<" "<<ans1<<endl;
return 0;
}
同问，缩点后答案应该是19867
by 一只小双鱼 @ 2019-03-25 14:43:44
```cpp
#include<bits/stdc++.h>
typedef long long LL;
typedef unsigned long long LLU;
const int inf=0x3f3f3f3f;
const int MAXN=100005;
const int mod=1000000007;
const int INF = 0x7fffffff ;
using namespace std;
struct edge
{
int to,next,fr;
};
edge e[30005],ne[30005];
int head[10005],dfn[10005],low[10005],col[10005],nhead[10005];
int a[10005],in[10005],vis[10005],sum[10005],w[10005];
int n,m,nn;
int cnt=0;
stack<int>s;
void add(int u,int v)
{
e[cnt].to=v;
e[cnt].fr=u;
e[cnt].next=head[u];
head[u]=cnt;
cnt++;
}
int ss=0;
void tarjan(int x)
{
ss++;
low[x]=dfn[x]=ss;
vis[x]=1;
s.push(x);
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(!dfn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(vis[v])
{
low[x]=min(low[x],dfn[v]);
}
}
if(dfn[x]==low[x])
{
int tmp;
while(tmp=s.top())
{
col[tmp]=x;
vis[tmp]=0;
s.pop();
if(x==tmp)break;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int u,v;
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>u>>v;
add(u,v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
{
int tmp=0,cnt=0;
for(int j=1;j<=n;j++)
{
if(col[j]==i)
{
if(tmp==0)
{
tmp=a[j]; cnt=1;
}
else
{
if(tmp>a[j])
{
cnt=1; tmp=a[j];
}
else if(tmp==a[j])
{
cnt++;
}
}
}
}
sum[i]=cnt;w[i]=tmp;
}
int x,y;
for(int i=1;i<=m;i++)
{
x=col[e[i].fr];y=col[e[i].to];
if(x!=y)
{
nn++;
ne[nn].fr=x;
ne[nn].to=y;
ne[nn].next=nhead[x];
nhead[x]=nn;
in[y]++;
}
}
int ans=0,ans1=1;
for(int i=1;i<=n;i++)
{
if(in[i]==0)
{
ans+=w[col[i]];
ans1*=sum[col[i]];
}
}
cout<<ans<<" "<<ans1<<endl;
return 0;
}
```
by 一只小双鱼 @ 2019-03-25 14:45:46
@[Dummerchen](/user/45619) 题目意思是要保证任意时刻每个点都有保安能到，当保安走到5时，他回不去3了，故3也要设个保安
by Albet @ 2022-05-12 08:47:20