正題

題目鏈接:http://noip.ybtoj.com.cn/contest/108/problem/4

---

題目大意

$n$個點，每次只封閉一個點，求剩下點對兩兩之間的最短路和。

---

解題思路

$Flody$中如果枚舉$k$時不管某一個點，那么就可以求不經(jīng)過那個點的路徑。考慮分治求解

我們每次處理到$[l,r]$時我們先計算出$[mid+1,r]$的貢獻（也就是枚舉這里的$k$），然后遞歸到$[l,mid]$的區(qū)間。處理完后清除$[mid+1,r]$的貢獻在處理$[l,mid]$的貢獻遞歸到$[mid+1,r]$區(qū)間。

這樣當$l=r$時只有$l$這個位置沒有處理貢獻，就可以統(tǒng)計答案了。

時間復雜度$O(n^3\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=321; ll n,f[N][N],ans,g[30][N][N]; void solve(ll dep,ll l,ll r){if(l==r){for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++){if(i==l||j==l)continue;if(f[i][j]<1e18)ans+=f[i][j];else ans--;}return;}ll mid=(l+r)>>1;memcpy(g[dep],f,sizeof(g[dep]));for(ll k=mid+1;k<=r;k++)for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);solve(dep+1,l,mid); memcpy(f,g[dep],sizeof(f));for(ll k=l;k<=mid;k++)for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);solve(dep+1,mid+1,r);return; } int main() {freopen("sum.in","r",stdin);freopen("sum.out","w",stdout);scanf("%lld",&n);for(ll i=1;i<=n;i++){for(ll j=1;j<=n;j++){scanf("%lld",&f[i][j]);if(f[i][j]==-1)f[i][j]=1e18;}}solve(0,1,n);printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的YbtOJ#20078-[NOIP2020模拟赛B组Day7]路径之和【分治,Flody】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。