ARC089 E : GraphXY(900)
作成日：2018.01.23
最終更新日：2018.01.23
問題概要
各辺に$100$以下の非負整数または$x$,$y$の重みがある頂点数が$300$以下の単純な有向グラフで、$1 \leq x \leq A$,$1 \leq y \leq B$を満たす$x$,$y$それぞれにおいて頂点$S$から頂点$T$への最短距離が$d_{x,y}$となるようなものが存在するか判定せよ。
また存在する場合はそのうちの1つを$S$,$T$とともに出力せよ。
制約
$1 \leq A,B \leq 10$
$1 \leq d_{x,y} \leq 100$
考え方
まず$S$から$T$へのパスのうちの一つを考える。
各辺の重みの条件からパスの長さは$ax+by+c$($a$,$b$,$c$は非負整数)の形で表せる。
問題の条件から$ax+by+c$$\geq d_{x,y}$であることが分かる。
最短経路となることがないパスは考える必要がないから、この形で表せる不等式のうちの少なくとも一つで等号が成立するようにする。
これは$x$,$y$が変数となっているから、$c$$= max(d_{x,y}$$-(ax+by))$を満たすように$a$,$b$,$c$を定めれば良い。
このように長さを定めたもので、$a$,$b$,$c$が非負整数であるものを考える。
$d$,$x$,$y$の制約から$a$,$b$,$c$は$100$以下であることが分かる。
先の等式を用いれば$a$,$b$を定めると$c$が一意に定まるが、調べるべき$a$,$b$の組は高々$101^2$個であるから全探索可能である。
これにより必要な長さのパスをすべて求めることができる。
但しこれは必要条件にすぎないから、$min(ax+by+c)$$= d_{x,y}$となるかを確かめなければならない。
1つでも満たさない$x$,$y$の組があれば、答えはImpossibleである。
この十分条件の確認も全探索でできる。
後はこのような長さのパスを含むグラフを構築できれば良い。
パスは最大で$101^2$本あることから、$101$個からなる2つの頂点集合間に上手く辺を張ることを考える。
この時、$a$及び$b$を頂点に対応付けられると構築しやすいのでそうなるようにする。
すなわち$a=0,1,...,100$を示す頂点と$b=0,1,...,100$を示す頂点を用意し、$a$,$b$間には対応する$c$を重みとする辺を張る。
$a$($b$)の対応は、その値を$S$($T$)から重み$x$($y)$をもつ辺何本分離れているかと解釈すれば達成できる。
ソースコード
マクロ等はこちら
int A,B;
int d[11][11];
const int C = 101;
int S = 1 , T = 2 * C;
int N = T , M = 2 * (C-1) + C * C;
int e[C][C];
int main(){
cin >> A >> B;
repp(i,1,A+1) repp(j,1,B+1) cin >> d[i][j];
repp(i,0,C) repp(j,0,C){
repp(x,1,A+1) repp(y,1,B+1) e[i][j] = max(e[i][j] , d[x][y]-i*x-j*y);
}
repp(x,1,A+1) repp(y,1,B+1){
int z = C;
repp(i,0,C) repp(j,0,C) z = min(z,e[i][j]+i*x+j*y);
if(z != d[x][y]) return cout << "Impossible" << endl , 0;
}
cout << "Possible" << endl;
cout << N << ' ' << M << endl;
repp(i,1,C){
cout << i << ' ' << i+1 << " X" << endl;
cout << C+i << ' ' << C+i+1 << " Y" << endl;
}
repp(i,0,C) repp(j,0,C) cout << i+1 << ' ' << N-j << ' ' << e[i][j] << endl;
cout << S << ' ' << T << endl;
return 0;
}解法まとめ
$0$以上$100$以下の整数$a$,$b$それぞれについて$e_{a,b}$$= max(0,$$d_{x,y}-ax-by)$とする。
$min(ax+by+e_{a,b})$$\neq d_{x,y}$となる$x$,$y$の組が存在すればImpossible、存在しなければPossibleが答えである。(11-19行)
グラフの構築は以下のように行う。
まず、重み$x$の辺$100$本からなる$S$を始点とする枝分かれのないグラフと、重み$y$の辺$100$本からなる$T$を終点とする枝分かれのないグラフを用意する。
そして$S$から$a$本の辺を辿った先の頂点$S_a$と$T$から$b$本の辺を遡った先の頂点$T_b$それぞれにおいて、$S_a$から$T_b$へ重み$e_{a,b}$の辺を張る。(20-26行)