Codeforces #244 Div2 C. Checkposts

CF244に参加。多少疲れてたとはいえこの出来は微妙。
http://codeforces.com/contest/427/problem/C

問題

N点とM有向辺からなるグラフが与えられる。
このうち何点かに警官の駐在所を置いてグラフ全体をパトロールしたい。
警官がある点をパトロールできるのは、駐在所からその点に移動でき、かつその点から駐在所に戻れる点である。

各点に駐在所を置く必要コストが与えられる。
グラフ全体をパトロールするのに駐在所を複数置く最小コストと、その置き方の組み合わせ数を答えよ。

解法

グラフを強連結成分分解する。
そして分解した各グループにおける最小コストの点および同着のコストの数を求めて、コストは加算、数は掛け合わせていく。

int N,M;
int A[100001];
ll mo=1000000007;

static const int MV = 100000;
vector<int> E[MV], RE[MV], NUM;

class G {
public:
	vector<vector<int> > SC;
	int NV,vis[MV],GR[MV];
	void init(int NV) { this->NV=NV; for(int i=0;i<MV;i++) { E[i].clear(); RE[i].clear(); }}
	void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); }
	void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); }
	void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu);
		FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);}
	void scc() {
		int c=0; SC.clear(); SC.resize(MV); NUM.clear();
		ZERO(vis); for(int i=0;i<NV;i++) if(!vis[i]) dfs(i);
		ZERO(vis); for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){ SC[c].clear(); revdfs(NUM[i],c++);}
		SC.resize(c);
	}
};

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	cin>>M;
	G g;
	g.init(N);
	FOR(i,M) {
		cin>>x>>y;
		g.add_edge(x-1,y-1);
	}
	
	ll cost=0,tot=1;
	int mic,num;
	g.scc();
	ITR(it,g.SC) {
		mic=1000000000,num=0;
		vector<int> V=*it;
		ITR(it2,V) {
			if(A[*it2]<mic) mic=A[*it2], num=0;
			num+=A[*it2]==mic;
		}
		cost+=mic;
		tot=tot*num%mo;
	}
	
	_P("%lld %lld\n",cost,tot);
}

まとめ

強連結成分分解に至るまでだいぶ時間食った…。