--- title: "Codeforce 472D Design Tutorial: Inverse the Problem 解析含快速解法(MST、LCA、思維)" description: "Codeforce 472D Design Tutorial: Inverse the Problem 解析含快速解法(MST、LCA、思維)" --- <!-- toc --> # Codeforce 472D Design Tutorial: Inverse the Problem 解析含快速解法(MST、LCA、思維) 今天我們來看看CF472D [題目連結](https://codeforces.com/problemset/problem/472/D) > **題目** 給你一個$n\times n$的矩陣代表點$i$到點$j$的最短距離。問是否可以造出一棵邊權為正的樹。 ### 前言 這題的輸入，輸入3e6個Integer經過實測就大概需要700ms以上了(如果沒開輸入優化好像還會直接TLE的樣子)。並且我一開始是用Prim's Algo去寫MST的，priority_queue用class來對pair<int,int> overload compare function，結果不管怎麼弄都TLE。最後放棄使用pair<int,int>，直接創一個struct，就AC了...。 看來Prim這種東西不但常數大，碰上一些奇怪的問題的機率還比較高阿...(**EDIT**:之後我在其他題目發現，如果把queue\<element\> q;宣告在非全域，那麼很有可能只要改動例如陣列size這種無關緊要的地方，就會造成TLE，當時的情況是每次bfs都在local宣告一次queue\<element\> q;) 乖乖用Kruskal就好了吧 (以下提供兩種方法的code) ### 想法 假設目前你只獲得了部分的樹(還有點沒有在樹裡面)，那麼這棵樹到那些還沒加入的點的最短距離「中」的最短的，必定是一條存在的連出去的邊，那麼我們當然需要把這條邊加進去。 以上的討論可以發現，這恰好就是Prim's Algo的過程阿!也就是這棵樹就是一個最小生成樹。 那我們可以選用兩種方法來造出這棵樹(Kruskal,Prim)。 剩下就是把最短路徑的矩陣造出來並且比對是否正確就好(使用LCA找到正確的路徑，並且記錄root到每個點的距離(也就是前綴和)，如此就可以$O(\lg n)$算出最短距離了)。 ### 想法2 這個想法網路上好像沒有人寫，但是比賽時很多人都是這樣寫的，很快。 首先確認$i\rightarrow i$的距離是$0$、$i\rightarrow j,\ i\neq j$的距離不為$0$、$dis(i\rightarrow j)==dis(j\rightarrow i)$。 接著沿用想法一，我們知道MST是存在的，而我們有的資訊只有那$n\times n$的距離矩陣，接下來只要測試任何邊(u,v)這條邊是可以在樹上就好(由於我們擁有的資訊只有這$n\times n$的矩陣，所以我們只要確認所有經過(u,v)的路徑都可以如矩陣上那樣就好)，最後只要把全部的(u,v) pair都測試過一遍，就結束了。 (這段話寫得比較模糊，建議直接看code) ### 程式碼(想法二): ```cpp= const int _n=2010; int t,n,d[_n][_n]; main(void) {cin.tie(0);ios_base::sync_with_stdio(0); cin>>n;rep(i,1,n+1)rep(j,1,n+1)cin>>d[i][j]; rep(i,1,n+1)rep(j,i,n+1)if((i==j and d[i][i]) or d[i][j]!=d[j][i] or (i!=j and d[i][j]==0)){cout<<"NO\n";return 0;} rep(i,1,n+1){ int r=1; rep(j,2,n+1)if(i!=j and d[r][i]>d[j][i])r=j; rep(k,1,n+1)if(abs(d[k][i]-d[k][r])!=d[i][r]){cout<<"NO\n";return 0;} }cout<<"YES\n"; return 0; } ``` 標頭、模板請點codepad看 [Submission](http://codepad.org/CSRVdWog) ### 程式碼(Kruskal): ```cpp= const int _n=2010,MAXB=12; int parent[_n], rank[_n]; inline void dsinit(int n) {for (int i = 0; i < n; i++)parent[i] = i;memset(rank, 0, sizeof rank);} inline int dsfind(int e) {return parent[e] == e ? e : parent[e] = dsfind(parent[e]);} inline void dsunion(int s1, int s2) {if (rank[s1] < rank[s2])swap(s1, s2);parent[s2] = s1;if (rank[s1] == rank[s2]) rank[s1]++;} //以上是dsu模板 int t,n,dep[_n],fa[_n][MAXB],d[_n][_n]; ll dis[_n]; vector<PII> G[_n]; struct E{ int f,t,w; bool operator<(const E& rhs) const {return w<rhs.w;} }; vector<E> e; bool vis[_n]; void dfs(int v,int faa,ll len){ dep[v]=dep[faa]+1;dis[v]=dis[faa]+len;fa[v][0]=faa; rep(i,0,SZ(G[v]))if(faa!=G[v][i].fi)dfs(G[v][i].fi,v,G[v][i].se); } void bfa(){ rep(j,1,MAXB)rep(i,1,n+1)if(~fa[i][j-1]) fa[i][j]=fa[fa[i][j-1]][j-1]; } int lca(int a,int b){ if(dep[a]<dep[b])swap(a,b); per(j,0,MAXB)if(~fa[a][j] and dep[fa[a][j]]>=dep[b])a=fa[a][j]; if(a==b)return a; per(j,0,MAXB)if(~fa[a][j] and fa[a][j]!=fa[b][j])a=fa[a][j],b=fa[b][j]; return fa[a][0]; } //以上基本上是lca模板 main(void) {cin.tie(0);ios_base::sync_with_stdio(0); cin>>n;rep(i,1,n+1)rep(j,1,n+1)cin>>d[i][j]; rep(i,1,n+1)rep(j,i,n+1)if((i==j and d[i][i]) or d[i][j]!=d[j][i] or (i!=j and d[i][j]==0)){cout<<"NO\n";return 0;} rep(i,1,n+1)rep(j,i+1,n+1)e.pb({i,j,d[i][j]}); sort(all(e)); dsinit(n); rep(i,0,SZ(e)){ int s1=dsfind(e[i].f),s2=dsfind(e[i].t); if(s1==s2) continue; dsunion(s1,s2); G[e[i].f].pb({e[i].t,e[i].w}); G[e[i].t].pb({e[i].f,e[i].w}); } dep[0]=-1;dfs(1,0,0);rep(i,1,n+1)rep(j,1,MAXB)fa[i][j]=-1; bfa(); rep(i,1,n+1)rep(j,i,n+1){ int l=lca(i,j); if(d[i][j]!=dis[i]+dis[j]-dis[l]*2){cout<<"NO\n";return 0;} }cout<<"YES\n"; return 0; } ``` 標頭、模板請點Submission看 [Submission](https://codeforces.com/contest/472/submission/90286933) ### 程式碼(Prim's): ```cpp= const int _n=2010,MAXB=13; int t,n,dep[_n],fa[_n][MAXB]; ll d[_n][_n],dis[_n]; vector<PII> G[_n]; bool vis[_n]; struct node{ int f,t,w; bool operator<(const node& rhs) const {return w>rhs.w;} }; //以上是真正有用到的struct class Cmp{ public: bool operator()(const PII& a,const PII& b) const {return d[a.fi][a.se]>d[b.fi][b.se];} }; //以上class，如前言所說，會造成TLE void dfs(int v,int faa,ll len){ dep[v]=dep[faa]+1;dis[v]=dis[faa]+len;fa[v][0]=faa; rep(i,0,SZ(G[v]))if(faa!=G[v][i].fi)dfs(G[v][i].fi,v,G[v][i].se); } void bfa(){ rep(j,1,MAXB)rep(i,1,n+1)if(~fa[i][j-1]) fa[i][j]=fa[fa[i][j-1]][j-1]; } int lca(int a,int b){ if(dep[a]<dep[b])swap(a,b); per(j,0,MAXB)if(~fa[a][j] and dep[fa[a][j]]>=dep[b])a=fa[a][j]; if(a==b)return a; per(j,0,MAXB)if(~fa[a][j] and fa[a][j]!=fa[b][j])a=fa[a][j],b=fa[b][j]; return fa[a][0]; } //以上基本上是lca模板 main(void) {cin.tie(0);ios_base::sync_with_stdio(0); cin>>n;rep(i,1,n+1)rep(j,1,n+1)cin>>d[i][j]; rep(i,1,n+1)rep(j,i,n+1)if((i==j and d[i][i]) or d[i][j]!=d[j][i] or (i!=j and d[i][j]==0)){cout<<"NO\n";return 0;} priority_queue<node> pq; pq.push({0,1}); while(!pq.empty()){ /*PII now;while(!pq.empty() and vis[(now=pq.top()).se])pq.pop(); if(pq.empty())break;*/ node now=pq.top(); pq.pop(); if(vis[now.t])continue; vis[now.t]=1; G[now.f].pb({now.t,d[now.f][now.t]}); //if(now.fi!=0)G[now.se].pb({now.fi,d[now.se][now.fi]}); rep(i,1,n+1)if(!vis[i])pq.push({now.t,i,d[now.t][i]}); } dep[0]=-1;dfs(1,0,0);rep(i,1,n+1)rep(j,1,MAXB)fa[i][j]=-1; bfa(); rep(i,1,n+1)rep(j,i,n+1){ int l=lca(i,j); if(d[i][j]!=dis[i]+dis[j]-dis[l]*2){cout<<"NO\n";return 0;} }cout<<"YES\n"; return 0; } ``` 標頭、模板請點Submission看 [Submission](https://codeforces.com/contest/472/submission/90284705)