D. Design Tutorial: Inverse the Problem 解析含快速解法(MST、LCA、思維)

Posted on By jeff

Codeforce 472D Design Tutorial: Inverse the Problem 解析含快速解法(MST、LCA、思維)

今天我們來看看CF472D
題目連結

題目
給你一個$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)

程式碼(想法二):

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

程式碼(Kruskal):

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

程式碼(Prim’s):

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

ojcode

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *