Codeforces #203 Div2. E. Wrong Floyd

Eも１発正解ではないけど自力で解けた。
http://codeforces.com/contest/350/problem/E

問題

N点・M辺からなる無向グラフに対し、以下の誤ったワーシャルフロイト法を適用する。

0～(N-1)のうちK個からなるA[i]が与えられ、WF法のもっとも外側のループはN点すべてではなく与えられたA[i]のみを適用してWF法を行う。

この条件で、正しく最短距離が与えられないような連結グラフを作れ。

解法

A[i]に含まれない(N-K)個の点の集合をB[i]とする。
問題のアルゴリズムで最短距離が正しく作れないためには、A[i]のうちどこか２点で、B[i]のいずれかを通らないと互いに移動経路が作れないような範囲で辺を張ればよい。

まず、連結グラフを作るために、(N-K)点のうち１つに残り(N-1)点すべてと辺を張る。
後は、A[0]をA[1]～A[K-1]と結ばないようにして、以下のように他の辺をM本まで増やしていけばよい。

• A[0]～A[K-1]とB[0]～B[N-K-1]を結ぶ。
• A[1]～A[K-1]同士を結ぶ
• B[0]～A[N-K-1]同士を結ぶ

これだけ結んでもM本に到達しないなら、A[0]とA[1]～A[K-1]を結ばないといけないので、題意を満たすグラフは作れない。

int N,M,K;
int A[500];
vector<int> B;
int mat[500][500];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>K;
	FOR(i,K) A[i]=GETi()-1;
	sort(A,A+K);
	FOR(i,N) {
		FOR(j,K) if(A[j]==i) break;
		if(j==K) B.push_back(i);
	}
	
	if(B.empty()) return _P("-1\n");
	FOR(x,N) if(x!=B[0]) M--,mat[B[0]][x]++,mat[x][B[0]]++;
	
	FOR(x,B.size()) FOR(y,K) if(M && mat[B[x]][A[y]]==0) M--,mat[B[x]][A[y]]++,mat[A[y]][B[x]]++;
	FOR(x,B.size()) for(y=x+1;y<B.size();y++) if(M && mat[B[x]][B[y]]==0) M--,mat[B[x]][B[y]]++,mat[B[y]][B[x]]++;
	for(x=1;x<K;x++) for(y=x+1;y<K;y++) if(M && mat[A[x]][A[y]]==0) M--,mat[A[x]][A[y]]++,mat[A[y]][A[x]]++;
	
	if(M) _P("-1\n");
	else FOR(x,N) for(y=x+1;y<N;y++) if(mat[x][y]) _P("%d %d\n",x+1,y+1);
}

まとめ

こういう問題は結構好き。