SRM 630 DIV1 Easy - Egalitarianism3 (××)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=13284&rd=16061

エッジのコストがわかっている、無向グラフが与えられる。
このとき、ノード間のコストが全て等しいサブグラフのうち、最も多いノード数を求める。

解き方


・エッジの数=ノード数N-1
・ノードA-ノードB-ノードCを考えた時、ノードA-ノードCとなるペアは存在しない。
・同じ距離の集合を考えた時、必ずハブとなるノードBが存在する。
・全てのノードをハブと考えた時、ノードA-ノードBの距離をdとすると
 ノードA-ノードCの距離が2dとなる集合のうち最大のものを求めればよい
・n=1のときの答えは1
・n=2のときの答えは2
・n>=2のとき答えは必ず2以上となる

コード


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 Egalitarianism3 {

public: int maxCities(int n, vector<int> a, vector<int> b, vector<int> len) {
if(n<=2)return n;

int g[n][n];
FORE(i,0,n)FORE(j,0,n)g[i][j]=1e+9;
FORE(i,0,a.size()){
g[a[i]-1][b[i]-1]=len[i];
g[b[i]-1][a[i]-1]=len[i];
}
FORE(k,0,n)FORE(i,0,n)FORE(j,0,n)g[i][j]=min(g[i][j],g[i][k]+g[k][j]);

int ret=2;
FORE(i,0,n){
FORE(j,0,n){
if(i!=j){
int d=g[i][j];
vector<int> tmp;
tmp.push_back(j);
FORE(k,0,n)if(g[i][k]==d && j!=k){
bool ok=true;
FORE(l,0,tmp.size())if(g[k][tmp[l]]!=2*d)ok=false;
if(ok)tmp.push_back(k);
}
ret=max(ret,(int)tmp.size());
}
}
}

return ret;
}

};
このエントリーをはてなブックマークに追加