kmjp's blog

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

Codeforces #349 Div1. B. World Tour

これは割と順調。
http://codeforces.com/contest/666/problem/B

問題

N頂点M辺の無向グラフが与えられる。
異なる4点(a,b,c,d)の組で、a→b→c→dとたどる最短経路が最長となるものを列挙せよ。

解法

b,cを総当たりし、候補となるa,dを求めよう。
まず前処理として、aの候補としてbまでの最短距離が長いもの上位3つを求めよう。
同様にdの候補としてcからの最短距離が長いもの上位3つを求める。

b,cを総当たりする際、a,dの候補のうち、a,b,c,dが互いに異なるようなものは必ず存在するのでそれらを総当たりし、最長となるものを求めよう。

int N,M;
vector<int> E[3030];
int dist[3030][3030];
vector<pair<int,int>> out[3030];
vector<pair<int,int>> in[3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		E[x].push_back(y);
	}
	FOR(x,N) FOR(y,N) dist[x][y]=101010;
	
	FOR(i,N) {
		dist[i][i]=0;
		queue<int> Q;
		Q.push(i);
		while(Q.size()) {
			x=Q.front();
			Q.pop();
			FORR(r,E[x]) if(dist[i][r]>dist[i][x]+1) dist[i][r]=dist[i][x]+1, Q.push(r);
		}
	}
	FOR(x,N) FOR(y,N) if(x!=y && dist[x][y]<=N) {
		out[x].push_back({dist[x][y],y});
		in[y].push_back({dist[x][y],x});
	}
	FOR(x,N) {
		sort(ALL(out[x]));
		reverse(ALL(out[x]));
		if(out[x].size()>3) out[x].resize(3);
		sort(ALL(in[x]));
		reverse(ALL(in[x]));
		if(in[x].size()>3) in[x].resize(3);
	}
	int ma=-1;
	int ret[4];
	FOR(x,N) FOR(y,N) if(x!=y && dist[x][y]<=N) {
		FORR(X,in[x]) {
			if(X.second==y) continue;
			FORR(Y,out[y]) {
				if(Y.second==x || Y.second==X.second) continue;
				int tot=dist[x][y]+X.first+Y.first;
				if(tot>ma) {
					ma=tot;
					ret[0]=X.second+1;
					ret[1]=x+1;
					ret[2]=y+1;
					ret[3]=Y.second+1;
				}
				break;
			}
		}
	}
	
	_P("%d %d %d %d\n",ret[0],ret[1],ret[2],ret[3]);
	
}

まとめ

こういうのは割と好き。