kmjp's blog

競技プログラミング参加記です

TopCoder SRM 665 Div2 Medium LuckyCycle

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良く出るよね。