Checkposts CodeForces - 427C (SCC裸题） HQG_AC

题意：

给你n个点，m条有向边，现在有你建立一些警察局。

每个点有一个建警察局的代价。

每个警察局能够保卫该点当且仅当警察局能到该点且能返回警察局。

现在问你建若干个警察局的最小代价和方案数是多少。

解析：

强连通裸题。

先把n个点做一个强连通。对于每个强连通分量，其中的点肯定能够互相到达。

强连通分量的建立可以通过$Kosaraju$ 和 $Tarjan$ 完成

于是我们在每个强连通中记录$Min[i]$和$Sum[i]$ 分别表示强连通分量i中的最小值和最小值的个数

设有k个强连通分量

$ans1=\sum\limits_{i=1}^kMin_i$
$ans2=\prod\limits_{i=1}^kSum_i$

$cout<<ans1<<"$ $"<<ans2<<endl ;$ (请勿复制)

最后提醒不要忘记mod!

Code:

$Kosaraju$

#include 
#include 
#include
#include
#include
#include
#include
#include
#define sqr(x) (x)*(x)
#define fz1(i,n) for (i=1;i<=n;i++)
#define fd1(i,n) for (i=n;i>=1;i--)
#define fz0g(i,n) for (i=0;i<=n;i++)
#define fd0g(i,n) for (i=n;i>=0;i--)
#define fz0k(i,n) for (i=0;i
#define fd0k(i,n) for (i=(long long)(n-1);i>=0;i--)
#define fz(i,x,y) for (i=x;i<=y;i++)
#define fd(i,y,x) for (i=y;i>=x;i--)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define rdst(st,len) {char ss[len];scanf("%s",ss);(st)=ss;}
using namespace std;
long long n,m,i,j,col[100005],mi[100005],f[100005],ans,ans2=1,vis[100005],cst[100005],x,y,cnt,mod=1e9+7;
vector<long long> bi[100005],nbi[100005],seq;
void dfs(int x)
{if (vis[x]) return;vis[x]=1;ff(nbi[x],it) dfs(*it);seq.push_back(x);
}
void dfs2(int x,int cnt)
{if (col[x]) return;col[x]=cnt;ff(bi[x],it) dfs2(*it,cnt);
}
int main()
{scanf("%I64d",&n);fz1(i,n) scanf("%I64d",&cst[i]);scanf("%I64d",&m);fz1(i,m){scanf("%I64d%I64d",&x,&y);bi[x].push_back(y);nbi[y].push_back(x);}fz1(i,n){if (!vis[i]){dfs(i);}}reverse(seq.begin(),seq.end());fz0k(i,n){if (!col[seq[i]]){cnt++;mi[cnt]=1ll<<55;dfs2(seq[i],cnt);}}fz1(i,n){if (cst[i]0;}if (cst[i]==mi[col[i]]){f[col[i]]++;}}fz1(i,cnt){ans+=mi[i];(ans2*=f[i])%=mod;}printf("%I64d %I64d\n",ans,ans2);return 0;
}

$Tarjan$

#include 
using namespace std ;
const int inf = 0x3f3f3f3f ;
const int N = 100010 ;
const int mod = 1000000007 ;
vector <int> G[N],link[N] ;
stack <int> S ;
long long dfn[N],low[N],sd[N],cost[N];
bool vis[N] ;
int tot=0,cnt,n,m,x,y ;
void tarjan(int now){dfn[now]=low[now]=++tot ;vis[now]=true;S.push(now) ;for (int i=0;iint to=G[now][i] ;if (!dfn[to]){tarjan(to) ;low[now]=min(low[now],low[to]) ;}if (dfn[to] && vis[to]) low[now]=min(low[now],low[to]) ;}if (low[now]==dfn[now]){sd[now]=++cnt ;vis[now]=false ;while(S.top()!=now){sd[S.top()]=cnt ;vis[S.top()]=false ;S.pop() ;}S.pop() ;}
}
int main(){scanf("%d",&n) ;for (int i=1;i<=n;i++) scanf("%d",&cost[i]) ;scanf("%d",&m) ;for (int i=1;i<=m;i++){scanf("%d%d",&x,&y) ;G[x].push_back(y) ;} memset(dfn,0,sizeof(dfn)) ;memset(low,0,sizeof(low)) ;memset(vis,false,sizeof(vis)) ;for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i) ;for (int i=1;i<=n;i++) link[sd[i]].push_back(i) ;long long ans=0,anssum=1 ;for (int i=1;i<=cnt;i++){int minn=inf,minnsum=0 ;for (int j=0;jint poi=link[i][j] ;if (minn>cost[poi]){minnsum=1  ;minn=cost[poi] ;}else if (minn==cost[poi]) minnsum++ ;}ans+=minn ;anssum=(anssum*minnsum)%mod ;}printf("%lld %lld",ans,anssum) ;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！