4がLuckyなのはどの文化圏なんだろうな。
http://community.topcoder.com/stat?c=problem_statement&pm=13958
問題
N頂点からなる連結した木を成すグラフが与えられる。
このグラフにおける辺は、無向辺でありかつその辺の重みは4か7である。
ここにまだ辺の無い2頂点間に1つ辺を足すことを考える。
当然その場合閉路が1個できる。
その際、閉路中で重み4の辺の数と重み7の辺の数が一致するような辺の追加の仕方があれば、それを1個答えよ。
解法
2頂点を総当たりし、それらが距離(辺の重みは無視して、辺1本距離1と考える)2以上でかつその頂点間における重み4の辺の数と7の辺の数の差が1なら、少ない方の辺を足せばよい。
N≦100なので、2頂点の間の距離はWarshall-Floyed法で求められる。
また各2頂点間の最短経路上にある辺の列挙もO(N^3)で出来るので、「重み4の辺の数と7の辺の数」も容易に求められる。
int num[101][101][2]; int dist[101][101]; class LuckyCycle { public: vector <int> getEdge(vector <int> edge1, vector <int> edge2, vector <int> weight) { int N=edge1.size()+1; int i,x,y; FOR(x,N) FOR(y,N) dist[x][y]=1010; FOR(x,N) dist[x][x]=0; FOR(i,N-1) dist[edge1[i]-1][edge2[i]-1]=dist[edge2[i]-1][edge1[i]-1]=1; FOR(i,N) FOR(x,N) FOR(y,N) dist[x][y]=min(dist[x][y],dist[x][i]+dist[i][y]); ZERO(num); FOR(i,N-1) { FOR(x,N) FOR(y,N) { if(dist[x][edge1[i]-1]+dist[y][edge2[i]-1]+1==dist[x][y]) num[x][y][(weight[i]==7)]++; if(dist[x][edge2[i]-1]+dist[y][edge1[i]-1]+1==dist[x][y]) num[x][y][(weight[i]==7)]++; } } vector<int> V; FOR(x,N) FOR(y,N) if(dist[x][y]>=2 && abs(num[x][y][0]-num[x][y][1])==1) { V.push_back(x+1); V.push_back(y+1); if(num[x][y][0]>num[x][y][1]) V.push_back(7); else V.push_back(4); break; } return V; } }
まとめ
CodeforcesでもLuck Number良く出るよね。