1. 首頁 > 生活百科 > >

Autobus 方法記錄( 二 )

生活百科Autobus 方法記錄

然后我們便得到了從點\(i\)到點\(j\)，經過\(1~k\)條邊的最短路 。然后我們再用\(ans[i][j]\)處理出這經過\(1~k\)條邊的方案中最短的情況 。（即最短路中的最短路）
綜合以上兩種情況，\(ans[i][j]\)就是最終的最短路了 。
如果想用以下代碼AC，需要做好常數優化 ， 比如\(O2\),\(register\)...
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int inf=1e9;const int N=75;int n,m,a,b,t;int k,q,c,d;int dis[N][N][N];//dis[i][j][k]:經過k條邊的前提下，i到j的最短路int ans[N][N];int minn(int a,int b){ return a<b?a:b;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)dis[i][j][k]=1e9; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans[i][j]=1e9; for(int i=1;i<=n;i++)for(int k=1;k<=n;k++)dis[i][i][k]=0; for(int i=1;i<=n;i++)ans[i][i]=0; for(int i=1;i<=m;i++) {scanf("%d%d%d",&a,&b,&t);dis[a][b][1]=minn(dis[a][b][1],t);ans[a][b]=minn(ans[a][b],t); } scanf("%d%d",&k,&q); if(k>=n) {for(int l=1;l<=n;l++)//l枚舉斷點{for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)//floyed標志性的三層for循環{ans[i][j]=minn(ans[i][j],ans[i][l]+ans[l][j]);//ans[i][j]根據floyed算法的定義，為i到j的最短路}}} } else {k=minn(k,n);for(int l=1;l<=n;l++)//l枚舉斷點{for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)//floyed標志性的三層for循環{for(int p1=1;p1<=k;p1++)//i到l可能的邊數{for(int p2=1;p2<=k&&p1+p2<=k;p2++)//l到j可能的邊數{dis[i][j][p1+p2]=minn(dis[i][j][p1+p2],dis[i][l][p1]+dis[l][j][p2]);}}}}}for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ans[i][j]=inf;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int l=1;l<=k;l++)ans[i][j]=minn(ans[i][j],dis[i][j][k]); } for(int i=1;i<=q;i++) {scanf("%d%d",&c,&d);if(c==d) puts("0");else if(ans[c][d]==inf) puts("-1");else printf("%d\n",ans[c][d]); } return 0;}繼續考慮，若我們能優化掉一層循環 ， 是不是就可以更安穩地A掉這道題了？
依然是以\(k\)作為突破口，有以下策略：“\(k\)越大，答案一定不會更差 。”現在我們要利用這種策略 ， 那么上文“令\(dis[i][j][k]\)表示經過\(k\)條邊的前提下，\(i\)到\(j\)的最短路”的定義就不合適了 。因為我們并不一定要把\(k\)條邊走完，\(k\)只是我們做選擇時的限制 。\(k\)越大 ， 說明限制越寬松 。
那么我們的解法便初具雛形了 。最外層從\(2\)到\(k\)枚舉每一種最大經過的邊限制 ， （為什么不從\(1\)開始枚舉？因為最多經過一條邊就是相鄰兩點間的距離了）在循環內跑一個\(floyd\) ， 總共四層循環 。
剩下的問題就是，轉移方程如何設計 。首先我們需要明確一點：\(k\)越大，說明選擇的面更廣 ， 所以每一次的答案，是從上一次的答案加上“新的選擇”生成的 。
b[i][j]=minn(b[i][j],a[i][l]+init[l][j]);這就是核心轉移方程，其中\(b\)數組記錄下一次的答案 ， \(a\)數組記錄這一次的答案，\(init\)數組是我們最開始輸入的圖，它正代表著“新的選擇” 。
為了維護這個轉移方程 ， 首先我們要把輸入的圖記錄下來——\(init\)數組在后續是不會改變的；然后用\(a,b\)兩個數組記錄這次的結果和下次的結果 。具體地講，就是每輪循環開始時將\(a\)賦給\(b\)，跑完\(floyd\)后再將\(b\)賦給\(a\) ， 如此往復 。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=75;const int inf=1e9;int n,m,u,v,t;int k,q,c,d;int init[N][N],a[N][N],b[N][N];int minn(int a,int b){ return a<b?a:b;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)init[i][j]=inf;//init數組初始化為一個極大值 for(int i=1;i<=n;i++)init[i][i]=0; for(int i=1;i<=m;i++) {scanf("%d%d%d",&u,&v,&t);init[u][v]=minn(init[u][v],t); } scanf("%d%d",&k,&q); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=init[i][j];//a數組最開始的狀態就是init k=minn(k,n);//同理，每個點最多到一次，所以和n取最小 for(int p=2;p<=k;p++) {for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)b[i][j]=a[i][j];//a賦給bfor(int l=1;l<=n;l++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)b[i][j]=minn(b[i][j],a[i][l]+init[l][j]);//核心：floydfor(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=b[i][j];//b賦給a } for(int i=1;i<=q;i++) {scanf("%d%d",&c,&d);if(c==d) puts("0");else if(a[c][d]==inf) puts("-1");else printf("%d\n",a[c][d]); } return 0;}還可以更快嗎？注意到轉移方程:
b[i][j]=minn(b[i][j],a[i][l]+init[l][j]);因為該轉移滿足結合律，所以考慮用廣義矩陣快速冪優化 。再想，上個方法的最外層循環是不是在枚舉\(k\)？那么，這個轉移從本質上來講就是求\(init[l][j]^k\).

推薦閱讀