問題
http://community.topcoder.com/stat?c=problem_statement&pm=6501&rd=9992
都市Antarcticaにポリスステーションを建てたい。
Antarcticaには複数の町があり、それぞれの町にポリスステーションを建てた時のコストがあらかじめわかっている。
ただし全ての町にポリスステーションを建てる必要はなく、その他のポリスステーションからその町に行くことができれば必要ない。
また、各町について一方通行でつながっているかどうかの情報も与えられる。
このとき、１つのポリスステーションを建てた時の平均コストが最小になるときの値を求める。
解き方
無向グラフではなく有向グラフの問題。
強連結である部分集合を求め、その他の集合からたどりつけない集合であればその部分集合から最小のコストを足す必要がある。
最後に、選ばれていない町のコストについて、平均が低くなるものについてのみコストを足してあげればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class AntarcticaPolice {
public:
double minAverageCost(vector<int> costs, vector<string> roads) {
int n=costs.size();
bool p[n][n];
FORE(i,0,n)FORE(j,0,n)p[i][j]=(roads[i][j]=='Y');
FORE(i,0,n)p[i][i]=1;
FORE(k,0,n)FORE(i,0,n)FORE(j,0,n)p[i][j]|=(p[i][k]&&p[k][j]);
int G=0,root[n];
memset(root,-1,sizeof(root));
FORE(i,0,n){
if(root[i]==-1){
root[i]=G;
FORE(j,0,n)if(i!=j && p[i][j] && p[j][i])root[j]=G;
G++;
}
}
int g[n][n];
memset(g,0,sizeof(g));
FORE(i,0,n)FORE(j,0,n)if(p[i][j])g[root[i]][root[j]]=1;
int used[n];
memset(used,0,sizeof(used));
FORE(i,0,G){
int in=0;
FORE(j,0,G)if(i!=j && g[j][i])in=1;
if(!in){
int tmp=-1;
FORE(j,0,n)if(root[j]==i && (tmp==-1 || costs[j]<costs[tmp]))tmp=j;
used[tmp]=1;
}
}
vector<int> others;
int sum=0,num=0;
FORE(i,0,n){
if(used[i])sum+=costs[i],num++;
else others.push_back(costs[i]);
}
sort(all(others));
double ret=(double)sum/num;
FORE(i,0,others.size()){
sum+=others[i],num++;
ret=min(ret,(double)sum/num);
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class AntarcticaPolice {
public:
double minAverageCost(vector<int> costs, vector<string> roads) {
int n=costs.size();
bool p[n][n];
FORE(i,0,n)FORE(j,0,n)p[i][j]=(roads[i][j]=='Y');
FORE(i,0,n)p[i][i]=1;
FORE(k,0,n)FORE(i,0,n)FORE(j,0,n)p[i][j]|=(p[i][k]&&p[k][j]);
int G=0,root[n];
memset(root,-1,sizeof(root));
FORE(i,0,n){
if(root[i]==-1){
root[i]=G;
FORE(j,0,n)if(i!=j && p[i][j] && p[j][i])root[j]=G;
G++;
}
}
int g[n][n];
memset(g,0,sizeof(g));
FORE(i,0,n)FORE(j,0,n)if(p[i][j])g[root[i]][root[j]]=1;
int used[n];
memset(used,0,sizeof(used));
FORE(i,0,G){
int in=0;
FORE(j,0,G)if(i!=j && g[j][i])in=1;
if(!in){
int tmp=-1;
FORE(j,0,n)if(root[j]==i && (tmp==-1 || costs[j]<costs[tmp]))tmp=j;
used[tmp]=1;
}
}
vector<int> others;
int sum=0,num=0;
FORE(i,0,n){
if(used[i])sum+=costs[i],num++;
else others.push_back(costs[i]);
}
sort(all(others));
double ret=(double)sum/num;
FORE(i,0,others.size()){
sum+=others[i],num++;
ret=min(ret,(double)sum/num);
}
return ret;
}
};