郑州网站设计推荐,公司网站后台怎么添加内容,discuz安装,东营网站关键词优化Part I-Introduction Floyd算法是一种求图上多源最短路径的算法#xff0c;适用于中小规模的图#xff0c;思维简单易懂。 Floyd算法的实质是#xff08;区间#xff09;动态规划#xff0c;在这里做一个简单的概述。 对于一个有\(n\)个结点的图#xff0c; 令\(dis[i][j…Part I-Introduction Floyd算法是一种求图上多源最短路径的算法适用于中小规模的图思维简单易懂。 Floyd算法的实质是区间动态规划在这里做一个简单的概述。 对于一个有\(n\)个结点的图 令\(dis[i][j]\)为结点\(i\)到结点\(j\)的最短路径长度。 首先将所有现成的边都存入\(dis\)其余的令其值\(\infty\)并使\(dis[i][i]0\)。 接着枚举中转点\(k\)那么 \[dis[i][j]\min\{dis[i][k]dis[k][j]\text{ | }k\in[1,n],k\ne i,k\ne j\}\] 代码实现 void Floyd()
{memset(dis,0x3f3f3f3f,sizeof(dis));for(int i1;in;i)for(int j1;jn;j)if(a[i][j]!0x3f3f3f3f)边(i,j)存在。dis[i][j]a[i][j];//a为现存的边。for(int i1;in;i) dis[i][i]0;for(int k1;kn;k)//枚举中转点。for(int i1;in;i)for(int j1;jn;j){if(ij||jk||ki) continue;dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);}
} Attention循环时\(k\)必须放在第一层。若将\(i\)置于第一层就会导致i-k-j的距离过早的确定下来可能会导致答案错误。 注其实最原始的Floyd中\(dis\)的定义是\(dis[i][j][k]\)表示结点\(i\)到结点\(j\)只经过结点\(i-k\)的最短路径。 则有\(dis[i][j][k]min(dis[i][j][k-1],dis[i][k][k-1]dis[k][j][k-1])\)降维得到现在的方程。 时间复杂度\(O(n^3)\)。 Part II-Sevral Simple Problems Floyd算法可以解决许多看似无法处理的问题。 Problem[1]:[USACO09JAN] Best Spot 链接https://www.luogu.org/problemnew/show/P2935 题面 此题较为简单算法流程 用Floyd处理出各个点间的最短路径。计算出每个点到各个Favorites的总距离。选出总距离最小的点输出即可。#includecstdio
#includealgorithm
#includecstring
using namespace std;
#define R registerint a[501][501];
int dis[501][501];
int fav[501];
int P,F,C;void Floyd()
{memset(dis,0x3f3f3f3f,sizeof(dis));for(R int i1;iP;i)for(R int j1;jP;j)if(a[i][j]!0x3f3f3f3f)dis[i][j]a[i][j];for(R int i1;iP;i) dis[i][i]0;for(R int k1;kP;k)for(R int i1;iP;i)for(R int j1;jP;j){if(ij||jk||ki) continue;dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);}
}signed main()
{scanf(%d%d%d,P,F,C);memset(a,0x3f3f3f3f,sizeof(a));for(R int i1;iF;i) scanf(%d,favi);for(R int u,v,w,i1;iC;i){scanf(%d%d%d,u,v,w);a[u][v]a[v][u]min(a[u][v],w);}Floyd();int minnum0x3f3f3f3f,minid;for(R int i1,sum0;iP;i,sum0){for(R int j1;jF;j)sumdis[i][fav[j]];if(summinnum) minnumsum,minidi;}printf(%d\n,minid);return 0;} Problem[2]:[JSOI2007]重要的城市 链接https://www.luogu.org/problemnew/show/P1841 题面 这一题比上一题略难如何记录中转点 Of course在Floyd的时候。 令\(c[i][j]\)为结点\(i,j\)之间的最短路的中转点若无则为0 在进行对\(dis[i][j]\)的更新之时我们不直接取min而是先判断以避免覆盖。 因为我们还要进行一个更重要的操作that is更新\(c[i][j]\) 分情况讨论 1.\(dis[i][j]dis[i][k]dis[k][j]\)需要更新此时结点\(i,j\)之间的最短路的中转点就要发生改变即\(c[i][j]k\)并更新\(dis[i][j]\)的值。2.\(dis[i][j]dis[i][k]dis[k][j]\) 这不仅说明原先的\(c[i][j]\)已经失效而且意味着此时已经不存在\(c[i][j]\)了并不需要中转点就有最短路了。因此令\(c[i][j]0\)。3.\(dis[i][j]dis[i][k]dis[k][j]\)此时的中转点无法得到更优的解忽略。这样我们就处理好了\(c\)。对于结果的处理可以利用桶排序的思想令\(res[c[i][j]]1\)。res[N]:bool 最后遍历\(res\)输出答案别忘了无解的处理。 #includecstdio
#includebitset
#includecstring
using namespace std;const int N205;
int c[N][N];
int f[N][N];
int n,m;void Solve()
{for(int i1;in;i) f[i][i]0;for(int k1;kn;k)for(int i1;in;i)for(int j1;jn;j){if(ij||jk||ik) continue;if(f[i][j]f[i][k]f[k][j])f[i][j]f[i][k]f[k][j],c[i][j]k;else if(f[i][j]f[i][k]f[k][j])c[i][j]0;}
}bool res[N],flag0;
signed main()
{memset(f,0x3f3f3f3f,sizeof(f));memset(c,0,sizeof(c));scanf(%d%d,n,m);for(int u,v,w,i1;im;i){scanf(%d%d%d,u,v,w);f[u][v]f[v][u]w;//f:dis}Solve();for(int i1;in;i)for(int j1;jn;j)res[c[i][j]]1;for(int i1;in;i)if(res[i]) printf(%d ,i),flag1;if(!flag) puts(No important cities.);return 0;
} Problem[3]:[NOI2007]社交网络 链接https://www.luogu.org/problemnew/show/P2047 题面 这题貌似比上一题更复杂——要进行路径计数。 令\(cnt[i][j]\)为结点\(i,j\)之间的最短路径条数。 还是在处理\(dis\)的时候处理\(cnt\)。 在分类讨论之前你需要知道一件事情 假设我们已经处理完了\(cnt[i][k]\)和\(cnt[k][j]\)那么怎么知道\(cnt[i][j]\)的值 对于\(cnt[i][k]\)中的每条路径与\(cnt[k][j]\)配对有\(cnt[k][j]\)条路径。 那么\(cnt[i][k]\)条一起配对就是\(cnt[i][k]\times cnt[k][j]\)条这就是\(cnt[i][j]\)的值。说白了就是乘法原理 那么再开始分类讨论 1.\(dis[i][j]dis[i][k]dis[k][j]\)又找到了一坨解\(cnt[i][j]cnt[i][k]*cnt[k][j]\)注意是。2.\(dis[i][j]dis[i][k]dis[k][j]\) 这代表有了新的解原先的答案不能再用了\(cnt[i][j]cnt[i][k]*cnt[k][j]\)注意是。3.\(dis[i][j]dis[i][k]dis[k][j]\)此时的中转点无法得到更优的解忽略。处理完\(cnt\)后那就意味着\(C_{s,t},C_{s,t}(v)\)什么的都出来了。 P.S.:建议cnt用double。 #includecstdio
#includealgorithm
#includecstring
using namespace std;const int N105;
int dis[N][N];
double cnt[N][N];
int n,m;signed main()
{memset(dis,0x3f3f3f3f,sizeof(dis));memset(cnt,0,sizeof(cnt));scanf(%d%d,n,m);for(int u,v,w,i1;im;i){scanf(%d%d%d,u,v,w);dis[u][v]dis[v][u]min(w,dis[u][v]);cnt[u][v]cnt[v][u]1;}for(int i1;in;i)dis[i][i]0;for(int k1;kn;k)for(int i1;in;i)for(int j1;jn;j){if(ij||ik||jk) continue;if(dis[i][j]dis[i][k]dis[k][j])cnt[i][j]cnt[i][k]*cnt[k][j];else if(dis[i][j]dis[i][k]dis[k][j]){dis[i][j]dis[i][k]dis[k][j];cnt[i][j]cnt[i][k]*cnt[k][j];}}for(int k1;kn;k){double ans0;for(int i1;in;i)for(int j1;jn;j){if(ij||ik||jk) continue;if(dis[i][j]dis[i][k]dis[k][j])anscnt[i][k]*cnt[k][j]*1.0/cnt[i][j];}printf(%.3lf\n,ans);}
} Part III-EXT:最小环问题 来看这么一个问题http://acm.hdu.edu.cn/showproblem.php?pid1599 题面 看似无从下手但仍然是Floyd 在更新\(dis\)前我们已经把\(1-(k-1)\)的情况处理好了。那么当前的最小环就是 \[\min\{a[i][k]a[k][j]dis[i][j]\}\] 先贴代码 #includecstdio
#includealgorithm
#includecstring
using namespace std;const int N105;
int a[N][N];
int dis[N][N];
int n,m;long long solve()
{long long min_circle0x3f3f3f3f;for(int k1;kn;k){for(int i1;ik;i)for(int ji1;jk;j)min_circlemin(min_circle,1ll*a[i][k]a[k][j]dis[i][j]);for(int i1;in;i)for(int j1;jn;j)dis[i][j]min(dis[i][j],dis[i][k]dis[k][j]);}return min_circle;
}signed main()
{while(scanf(%d%d,n,m)!EOF){memset(a,0x3f3f3f3f,sizeof(a));for(int u,v,w,i1;im;i){scanf(%d%d%d,u,v,w);a[u][v]a[v][u]min(a[u][v],w);}for(int i1;in;i)for(int j1;jn;j)dis[i][j]a[i][j];long long ressolve();if(res!0x3f3f3f3f) printf(%lld\n,res);else puts(Its impossible.);}return 0;
} 值得注意的是\(i,j\)的循环范围的控制因为\(i,j,k\)不能相同。 至于为什么先处理最小环在更新路径当然是为了使\(dis[i][j]\)不经过\(k\)啊。 转载于:https://www.cnblogs.com/-Wallace-/p/11165803.html
