TopCoder SRM 312 Div1 Medium AntarcticaPolice

問題

n個の都市が、一方通行の道でつながっている。
それぞれの都市に警察を置くコストがcosts[i]により与えられる。

全ての都市に、「その都市または、その都市へ行くことが出来る都市のどれかひとつ」に警察が置かれている状態にしたい。
この状態で、警察を置くコストの、警察署一つあたりのコストの最小値を求めよ。

制約条件

n≦50
costs[i]≦1000

方針

強連結成分分解を行う。
SCC後のグラフはDAGになっていて、DAGの根に当たるノードには必ず警察署を作らなければならない。

根に当たるノードが複数の頂点からできていたら、その中で最も安いコストの都市に警察署を作ればよい。
その後、使ってないノードを適当に追加して平均を小さくできるか見る。

これは、使ってないノードをコストの小さい順にソートして、平均が下がる間そのノードを貪欲に使うことにすればいい。

ソースコード

強連結成分分解は蟻本実装。

const int MAX_V=100;
int V;
vi G[MAX_V], rG[MAX_V], vs;
bool used[MAX_V];
int cmp[MAX_V];

void add_edge(int from,int to){
	G[from].pb(to);
	rG[to].pb(from);
}
void dfs(int v){
	used[v]=1;
	rep(i,G[v].size())if(!used[G[v][i]])dfs(G[v][i]);
	vs.pb(v);
}
void rdfs(int v,int k){
	used[v]=1;
	cmp[v]=k;
	rep(i,rG[v].size())if(!used[rG[v][i]])rdfs(rG[v][i],k);
}
int scc(){
	memset(used,0,sizeof(used));
	vs.clear();
	rep(v,V)if(!used[v])dfs(v);
	memset(used,0,sizeof(used));
	int k=0;
	for(int i=vs.size()-1;i>=0;i--){
		if(!used[vs[i]])rdfs(vs[i],k++);
	}
	return k;
}

class AntarcticaPolice {
	public:
	double minAverageCost(vector <int> costs, vector <string> roads) 
	{
		V=costs.size();
		rep(i,V)G[i].clear(), rG[i].clear();
		rep(i,V)rep(j,V)if(roads[i][j]=='Y')add_edge(i,j);
		
		int k=scc(), deg[50]={};
		bool e[50][50]={};
		rep(i,V)rep(j,V)if(roads[i][j]=='Y')e[cmp[i]][cmp[j]]=1;
		rep(i,k)rep(j,k)if(i!=j&&e[i][j])deg[j]++;
		
		bool use[50]={};
		int sum=0, m=0;
		rep(i,k)if(deg[i]==0){
			int mni=-1;
			rep(j,V)if(cmp[j]==i){
				if(mni<0||costs[j]<costs[mni])mni=j;
			}
			use[mni]=1;
			sum+=costs[mni];
			m++;
		}
		
		vi v;
		rep(i,V)if(!use[i])v.pb(costs[i]);
		sort(all(v));
		double ans=sum*1.0/m;
		rep(i,v.size()){
			if((sum+v[i])/(m+1.0)<ans){
				ans=(sum+v[i])/(m+1.0);
				sum+=v[i];
				m++;
			}
		}
		return ans;
	}
};