Floyd算法的证明
void floyd()//三层循环实现floyd算法 { for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); }
Floyd的运用
1.牛的旅行（最短路）
#include<bits/stdc++.h> #define x first #define y second using namespace std; const int N=160; const double INF=1e20; typedef pair<int,int> pii; pii p[N]; char g[N][N]; double dist[N][N]; double maxd[N]; int n; double get_dist(pii a,pii b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int main() { cin>>n; for(int i=0;i<n;i++) cin>>p[i].x>>p[i].y; for(int i=0;i<n;i++) cin>>g[i]; for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(i!=j) { if(g[i][j]=='1') dist[i][j]=get_dist(p[i],p[j]);//假如是相连的可以直接算两点间的距离 else dist[i][j]=INF;//反之为正无穷 } for(int k=0;k<n;k++)//用Floyd更新两两的最短距离 for(int i=0;i<n;i++) for(int j=0;j<n;j++) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]); for(int i=0;i<n;i++)//更新距离i这个点的最长距离 for(int j=0;j<n;j++) if(dist[i][j]<INF)//假如在同个牧场才更新 maxd[i]=max(maxd[i],dist[i][j]); double res1=0; for(int i=0;i<n;i++) res1=max(res1,maxd[i]);//求一遍每个牧场的最长直径，因为结果肯定大于两个牧场的直径 double res2=INF; for(int i=0;i<n;i++)//枚举两个点相连 for(int j=0;j<n;j++) if(dist[i][j]>=INF)//假如不在一个牧场才相连 res2=min(res2,get_dist(p[i],p[j])+maxd[i]+maxd[j]);//假如这两个点相连 printf("%lf\n",max(res1,res2));//输出二者的最大 return 0; }
2.排序（传递闭包）
#include<bits/stdc++.h> using namespace std; const int N=30; int n,m; bool dist[N][N]; bool st[N]; void floyd()//用Floyd更新其他的点 { for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) dist[i][j]|=dist[i][k]&&dist[k][j]; } int check() { for(int i=0;i<n;i++) if(dist[i][i]) return 2;//假如自己小于自己则有矛盾 for(int i=0;i<n;i++) for(int j=0;j<i;j++) if(!dist[i][j]&&!dist[j][i])//假如i和j的关系还没确定 return 0; return 1;//假如关系可以确定 } char print()//找最小的数 { for(int i=0;i<n;i++) if(!st[i])//假如还没输出 { bool f=true;//用来标记是不是小于所有数 for(int j=0;j<n;j++) if(!st[j]&&dist[j][i])//假如大于其中一个数了，说明这个数不是小于所有数 { f=false; break; } if(f)//假如这个数是小于所有数了，则返回 { st[i]=true; return 'A'+i; } } } int main() { while(cin>>n>>m,n||m) { memset(dist,0,sizeof dist); int type=0,t; for(int i=1;i<=m;i++) { char str[5]; cin>>str; int a=str[0]-'A',b=str[2]-'A'; if(!type) { dist[a][b]=1;//标记a<b floyd();//用floyd更新一遍 type=check();//判断一下这一步 if(type) t=i;//假如可以确定，则记录这一步 } } if(!type) puts("Sorted sequence cannot be determined.");//假如不能确定 else if(type==2) printf("Inconsistency found after %d relations.\n",t);//假如有矛盾 else//假如可以输出 { memset(st,0,sizeof st);//先记录每个点都没输出 printf("Sorted sequence determined after %d relations: ",t); for(int i=0;i<n;i++) cout<<print();//循环n次输出n个数 puts("."); } } return 0; }
3.观光之旅（找最小环）
每次floyd更新最大值为k的环，然后存下来
#include<bits/stdc++.h> using namespace std; const int N=110; int d[N][N],dist[N][N]; int n,m; int path[N],cnt; int pos[N][N]; void get_path(int i,int j)//用来获取路径 { if(pos[i][j]==0) return;//假如没中间元素了 int k=pos[i][j];//获取他的中间转移过来的元素 get_path(i,k);//过去左半边 path[cnt++]=k;//把中间元素放进路径中 get_path(k,j);//获取右半边元素 } int main() { memset(d,0x3f,sizeof d); cin>>n>>m; for(int i=1;i<=n;i++) d[i][i]=0;//自己到自己的环为0 while(m--) { int a,b,c; cin>>a>>b>>c; d[a][b]=d[b][a]=min(d[a][b],c); } memcpy(dist,d,sizeof dist);//把d复制给folyd更新的dist int res=0x3f3f3f3f; for(int k=1;k<=n;k++) { for(int i=1;i<k;i++)//用来求环中最大元素是k的环 for(int j=i+1;j<k;j++) if((long long)dist[i][j]+d[j][k]+d[k][i]<res)//假如从i~j+d[j][k]+d[k][i],也就是构成一个环了，这个环的边权小于答案这更新进来 { res=dist[i][j]+d[i][k]+d[k][j];//更新最小值 cnt=0;//从新记录路径 path[cnt++]=k; path[cnt++]=i; get_path(i,j);//获取i~j的路径经过的点 path[cnt++]=j; } for(int i=1;i<=n;i++)//用Floyd更新最短路径 for(int j=1;j<=n;j++) if(dist[i][j]>dist[i][k]+dist[k][j]) { pos[i][j]=k;//距离ij由中间点k更新过来 dist[i][j]=dist[i][k]+dist[k][j]; } } if(res==0x3f3f3f3f) puts("No solution."); else { for(int i=0;i<cnt;i++) cout<<path[i]<<' '; puts(""); } return 0; }
4.牛站（快速幂求n次方+用map离散化）
离散数学的图论中经过k条边就是恰好矩阵的k次方的最小值
#include<bits/stdc++.h> using namespace std; const int N=210; int k,n,m,S,E; unordered_map<int,int> id; int g[N][N],res[N][N]; void mul(int c[][N],int a[][N],int b[][N])//状态计算 { static int temp[N][N]; memset(temp,0x3f,sizeof temp); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) temp[i][j]=min(temp[i][j],a[i][k]+b[k][j]);//假如a中的i~k+b的k~j小于我i~j则更新 memcpy(c,temp,sizeof temp);//把答案传回去 } void qmi() { memset(res,0x3f,sizeof res); for(int i=1;i<=n;i++) res[i][i]=0;//自己到自己也合法 while(k) { if(k&1) mul(res,res,g);//res=res*g mul(g,g,g);//g=g*g k>>=1; } } int main() { memset(g,0x3f,sizeof g); cin>>k>>m>>S>>E; if(!id.count(S)) id[S]=++n;//假如S还没离散化，就离散化 if(!id.count(E)) id[E]=++n;//假如E还没离散化，就离散化 S=id[S],E=id[E];//等于离散化后的值 while(m--) { int a,b,c; cin>>c>>a>>b; if(!id.count(a)) id[a]=++n;//假如a还没离散化，就离散化 if(!id.count(b)) id[b]=++n;//假如b还没离散化，就离散化 a=id[a],b=id[b];//等于离散化后的值 g[a][b]=g[b][a]=min(g[a][b],c); } qmi();//快速幂 cout<<res[S][E]<<endl; return 0; }
