J-xay loves Floyd

ANJHZ題解
abcdhhhh_題解

如果${\text{d}}_{i,j}={\text{w}}_{i,j}$,那么按照題意中的算法仍然能得到正確的結果。此時記${\text{can}}_{i,j}=1$。

如果存在$v$，使得①${\text{can}}_{i,v}=1$②${\text{can}}_{v,j}=1$③$v$在$i$到$j$的任意一條最短路上，那么${\text{can}}_{i,j}=1$。

直接這么算$can[i][j]$復雜度太高，我們注意到$can[i][?]$，$can[?][j]$的運算本質上是集合求交，可以利用bitset維護。
將$can[i][?]$記為bitset<N> fr[i]，$can[?][j]$記為bitset<N>to[j]

同時，枚舉$s$,則$s$到$j$的所有最短路經過的點集${\text{pot}}_j$也可以通過bitset維護，具體做法是每次枚舉一個$s$,就重新把頂點按照到$s$的最短路長度排序，從小到大計算${\text{pot}}_j$。如果${\text{d}}_{s,k}+{\text{w}}_{k,j}={\text{d}}_{s,j}$,則${\text{pot}}_j|={\text{pot}}_k$

時間復雜度$O(nm\log m+\frac{n^{2}w}{w})$

Code

#include<bits/stdc++.h> using namespace std; using ll=long long; template <class T=int> T rd() {T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg; } const int N=2005,M=5005; int h[N],e[M],ne[M],w[M],idx; void add(int a,int b,int c){e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;} int d[N][N]; int n,m; bool st[N]; bitset<N> pot[N],fr[N],to[N];void dij(int s,int d[]) {memset(st,0,sizeof st);priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;q.push({d[s]=0,s});while(q.size()){int u=q.top().second;q.pop();if(st[u]) continue;st[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(d[v]>d[u]+w[i]) {d[v]=d[u]+w[i];q.push({d[v],v});}}}for(int i=h[s];i!=-1;i=ne[i]){int v=e[i];if(w[i]==d[v]) fr[s][v]=to[v][s]=1;} } int solve(int s) {static int id[N];for(int i=1;i<=n;i++){pot[i].reset();pot[i].set(i);}for(int i=1;i<=n;i++) id[i]=i;sort(id+1,id+1+n,[&](const int i,const int j){return d[s][i]<d[s][j];});for(int i=1;i<=n;i++){int u=id[i];for(int i=h[u];i!=-1;i=ne[i]){int v=e[i];if(d[s][u]+w[i]==d[s][v]) pot[v]|=pot[u];}}for(int i=1;i<=n;i++)if(d[s][i]==0x3f3f3f3f||(pot[i]&fr[s]&to[i]).count()) fr[s][i]=to[i][s]=1;return fr[s].count(); } int main() {n=rd(),m=rd();memset(d,0x3f,sizeof d);memset(h,0xff,sizeof h);for(int i=1;i<=n;i++){fr[i].reset();fr[i][i]=1;to[i].reset();to[i][i]=1;}while(m--){int u=rd(),v=rd(),c=rd();add(u,v,c);}for(int i=1;i<=n;i++) dij(i,d[i]);int ans=0;for(int i=1;i<=n;i++) ans+=solve(i);printf("%d\n",ans); }

總結

以上是生活随笔為你收集整理的2021牛客暑期多校训练营7 J-xay loves Floyd（最短路+bitset优化集合交）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。