CF 716 D - Complete The Graph
問題
問題概要
頂点辺の無向グラフがある。辺にはそれぞれ重みがあり、その重さは正の整数である。いくつかの辺の重みがわからなくなってしまったので、その辺に重みを付け直したい。ただし、頂点から頂点への最短経路はでなければならない。
そのような方法がない場合はNO
と出力し、ある場合にはYES
と出力して全ての辺の重さを出力せよ。
アイデア
この問題は不可能な状況を考えなければ単純に考えていくことが出来る。というわけでまずは解が存在する時はどのような状況なのかを考えてみる。
まず、重みがわからなくなってしまった辺を存在しないものとして考え、既にわかっている辺のみでのからへの最短経路を計算してみて、その距離が未満ならばその他の辺をどのように設定しても不可能であることが明らかなので、解が存在しないということがわかる。
そして、次に重みがわからなくなってしまった辺の重さを全てに設定して最短経路を計算してみる。すると、からへの最短経路としてあり得る値の中で最小値が求まることは簡単にイメージできる。つまり、この値がよりも大きくなってしまったらこれ以上小さく出来ないのだからその時も解が存在しないということがわかる。
この2つの判定に引っかからなければ、何らかの形で解が存在するということになる。全てのからへのパス上に未定辺が1つあると仮定したときに、はじめは全ての未定の辺に重さ1を割り当てておいて最短経路を探す。それがに一致すれば終了し、一致しない時は最短経路上の未定だったどれか1つの辺の重さを1増やす。すると、経路は変わるかもしれないが、最短経路は1増えることになる。これを繰り返していくことでいずれは最短経路の距離はになっていくのが分かる。
それでは、どのようにして効率よく重みを割り当てていけばよいのかということを考えてみる。上で述べたことに似たようなことをする。まずは未定辺をはじめ全て重さ1にしておき、まずその状態でからへの最短経路を求める。この経路上に未定辺が無かった場合、この経路の長さがでなければならない。もしある時には、その経路長は未満であるはずである。
ここで、最短経路上には無い未定辺の重みをに再設定して再びからへの最短経路を求める。そして、その最短経路上の未定辺を上手く設定して最短経路長をになるようにしていきたい。どのようにするかというと、最短経路長が未満である限り、その経路上の1つの未定辺を適当にいじってになるようにとりあえずしてみる。そしてまた最短経路を計算し直す。これを繰り返していくことでいずれはへ近づいていき一致するはずである。そして、この繰り返しの回数は回に収まる。最初に発見した最短経路上の辺しかいじらないので、変更することになる辺の個数が本になる。そしてこの辺の重みの変更は各辺に対して1回ずつしか行われないからである。
ということで最短経路の計算にDijkstra法を利用することで全体の計算量はとなり、間に合う。Editorialには、でも実は解けるということについて言及されている。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second typedef pair<int,int> pi; const int N=1000, M=10000; const ll INF=123456789012345LL; int U[M], V[M], W[M]; struct edge{int to,cost;}; vector<edge> G1[N], G2[N]; ll d1[N], d2[N]; int par[N]; // 0:存在しない, -1:未定辺, -2:最短経路に含まれる未定辺 ll ans[N][N]={0}; int main() { int n,m,L,s,t; scanf(" %d %d %d %d %d", &n, &m, &L, &s, &t); rep(i,m) { int u,v,w; scanf(" %d %d %d", &u, &v, &w); if(w==0) { G2[u].pb(edge{v,1}); G2[v].pb(edge{u,1}); ans[u][v]=ans[v][u]=-1; } else { G1[u].pb(edge{v,w}); G1[v].pb(edge{u,w}); G2[u].pb(edge{v,w}); G2[v].pb(edge{u,w}); ans[u][v]=ans[v][u]=w; } U[i]=u; V[i]=v; W[i]=w; } priority_queue<pi,vector<pi>,greater<pi>> que; // 未定辺を含まないグラフでの最短経路 // dijkstra fill(d1,d1+N,INF); d1[s]=0; que.push(pi(0,s)); while(!que.empty()) { pi p=que.top(); que.pop(); int v=p.se; if(d1[v]<p.fi) continue; rep(i,G1[v].size()) { edge e=G1[v][i]; if(d1[e.to]>d1[v]+e.cost) { d1[e.to]=d1[v]+e.cost; que.push(pi(d1[e.to],e.to)); } } } if(d1[t]<L) { printf("NO\n"); return 0; } if(d1[t]==L) { printf("YES\n"); rep(i,m) { int u=U[i], v=V[i]; ll d=ans[u][v]; if(d<0) d=INF; printf("%d %d %lld\n", u, v, d); } return 0; } // 未定辺の重みを全て1にしたグラフでの最短経路 // dijkstra fill(d2,d2+N,INF); d2[s]=0; que.push(pi(0,s)); memset(par,-1,sizeof(par)); while(!que.empty()) { pi p=que.top(); que.pop(); int v=p.se; if(d2[v]<p.fi) continue; rep(i,G2[v].size()) { edge e=G2[v][i]; if(d2[e.to]>d2[v]+e.cost) { d2[e.to]=d2[v]+e.cost; que.push(pi(d2[e.to],e.to)); // 経路復元のために親を記録 par[e.to]=v; } } } if(d2[t]>L) { printf("NO\n"); return 0; } int now=t; while(now!=s) { int nx=par[now]; if(ans[now][nx]==-1) ans[now][nx]=ans[nx][now]=-2; now=nx; } // 最短経路に関係ない未定辺を全てINFに設定 rep(i,N)rep(j,N) { if(ans[i][j]==-1) ans[i][j]=INF; } // もどしておく rep(i,N)rep(j,N) { if(ans[i][j]==-2) ans[i][j]=-1; } // 最短経路がLに一致するまでやる while(1) { // dijkstra fill(d2,d2+N,INF); d2[s]=0; que.push(pi(0,s)); memset(par,-1,sizeof(par)); while(!que.empty()) { pi p=que.top(); que.pop(); int v=p.se; if(d2[v]<p.fi) continue; rep(i,G2[v].size()) { edge e=G2[v][i]; int cost=ans[v][e.to]; if(d2[e.to]>d2[v]+abs(cost)) { d2[e.to]=d2[v]+abs(cost); que.push(pi(d2[e.to],e.to)); // 経路復元のために親を記録 par[e.to]=v; } } } if(d2[t]==L) break; now=t; while(now!=s) { int nx=par[now]; // 未定辺 if(ans[now][nx]<0) { ll dist=abs(ans[now][nx]); ans[now][nx]=ans[nx][now]=dist+(L-d2[t]); break; } now=nx; } } printf("YES\n"); rep(i,m) { int u=U[i], v=V[i]; ll d=abs(ans[u][v]); printf("%d %d %lld\n", u, v, d); } return 0; }