CodeForces - 427C Checkposts (强连通分量)

本文主要是介绍CodeForces - 427C Checkposts (强连通分量)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://codeforces.com/problemset/problem/427/C
题意：一共给你 $N$ 个点， $M$ 条有向边。其中每个点都有其自己对应的权值，作为城市的市长，你希望设定警察局来保护所有的城市。如果我们在点 $i$ 处设立了一个警察局，那么其点 $i$ 是被保护的，而且如果一个点 $j$ ，能够保证有路径从 $i$ 到 $j$ ，并且能够保证有路径从 $j$ 回到 $i$ ，那么点j也是被保护的。
问将所有城市都保护起来的最小花费，以及对应最小花费有多少种设定的方式。

题意说能从 $i$ 到 $j$ 且能从 $j$ 到 $i$ 即很明显地表示这是一个强连通分量，那么对每一个强连通块Tarjan缩点后，这个块的权值就是这个块包含的所有点钟权值最小的那个记为 $p[i]$ ，然后将所有块的权值加起来就是最小花费，即

a n s 1 = \sum p [i]

$ans1=\sum p[i]$
而方案数只需在更新每个强连通块的权值时，记录能取到最小值的点有几个记为pp[i]，最后将所有块的

pp[i] p p [ i ] $pp[i]$ 相乘就是方案数，即

a n s 2 = \prod p p [i]

$ans2=\prod pp[i]$

注意一点就是 $ans1$ 不取模， $ans2$ 要取模。

#include<iostream>
#include<cstdio>
#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>using namespace std;
const int maxn=100010,maxm=300010;
int dfn[maxn],low[maxn],head[maxn],color[maxn],a[maxn],pp[maxn];
int n,m,k,x,y,cnt,deep;
long long ans1,ans2=1,p[maxn];bool vis[maxn];
struct edge{int v,w,next;
}e[maxm];stack<int> st;void addedge(int u,int v){e[k].v=v;e[k].next=head[u];head[u]=k++;}void tarjan(int u)
{deep++;dfn[u]=deep;low[u]=deep;vis[u]=1;st.push(u);for(int i=head[u];~i;i=e[i].next){int v=e[i].v;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else{if(vis[v]){low[u]=min(low[u],low[v]);}}}if(dfn[u]==low[u]){cnt++;color[u]=cnt;vis[u]=0;p[cnt]=a[u];pp[cnt]=1;while(st.top()!=u){color[st.top()]=cnt;vis[st.top()]=0;if(a[st.top()]<p[cnt]){p[cnt]=a[st.top()];pp[cnt]=1;}else if(a[st.top()]==p[cnt])pp[cnt]++;st.pop();}st.pop();}
}
int main()
{memset(head,-1,sizeof(head));scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);addedge(x,y);}for(int i=1;i<=n;i++){if(!dfn[i])tarjan(i);}for(int i=1;i<=cnt;i++){ans1+=p[i];ans2*=pp[i];ans2%=1000000007;}printf("%lld %lld",ans1,ans2%1000000007);return 0;
}