应用

1.最短路

2.传递闭包

3.找最小环（一般正权图）

4.恰好经过k条边的最短路 倍增

floyd的证明为dp

状态表示d[ k , i , j ]为所有从 i 出发 最终走到 j 且中间只经过节点编号不超过k的所有路径

属性求 min

状态计算

把集合分成两部分

(1)所有包含节点k的路径 d[ k-1 , i , k ] + d[ k-1, k, j ]

(2)所有不含节点k的路径 d[ k-1 , i, j ]

d[ k, i, j ]=min(d[ k-1, i ,k]+d[ k-1 , k, j ],d[ k-1 , i, j ])

优化第一维就结束了

1.牛的旅行

讯享网

1125. 牛的旅行 - AcWing题库

#include <bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int,int> PII; const int N=150; const double INF=1e20; int n; PII q[N]; char g[N][N]; double d[N][N],maxd[N]; double getdis(PII a,PII b) { double dx=a.x-b.x,dy=a.y-b.y; return sqrt(dx*dx+dy*dy); } int main() { cin>>n; for(int i=0;i<n;i++) { cin>>q[i].x>>q[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') d[i][j]=getdis(q[i],q[j]); else d[i][j]=INF; } for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); for(int i=0;i<n;i++) for(int j=0;j<n;j++) { if(d[i][j]<INF) { maxd[i]=max(maxd[i],d[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(d[i][j]>=INF) { res2=min(res2,getdis(q[i],q[j])+maxd[i]+maxd[j]); } printf("%lf\n",max(res1,res2)); return 0; } 

2.排序（传递闭包）

g(i,j)是无权图 0 表示没边 1表示有

步骤：1.d(i,j)=g(i,j)

           2.Floyd if( i 能到 k , k 能到 j ) d(i,j)=1

讯享网#include<bits/stdc++.h> using namespace std; const int N=30; int n,m; bool dist[N][N]; bool st[N]; void 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]) 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; 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(); puts("."); } } return 0; } 

本题还能优化

3. 观光之旅

344. 观光之旅 - AcWing题库

#include <bits/stdc++.h> using namespace std; const int N=110,INF=0x3f3f3f3f; int n,m; int d[N][N],g[N][N]; int pos[N][N]; int path[N],cnt; 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() { cin>>n>>m; memset(g,0x3f,sizeof g); for(int i=1;i<=n;i++) g[i][i]=0; while(m--) { int a,b,c; cin>>a>>b>>c; g[a][b]=g[b][a]=min(g[a][b],c); } memcpy(d,g,sizeof d); int res=INF; for(int k=1;k<=n;k++) { for(int i=1;i<k;i++) { for(int j=i+1;j<k;j++) if((long long)d[i][j]+g[j][k]+g[k][i]<res) { res=d[i][j]+g[j][k]+g[k][i]; cnt=0; path[cnt++]=k; path[cnt++]=i; get_path(i,j); path[cnt++]=j; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(d[i][j]>d[i][k]+d[k][j]) { d[i][j]=d[i][k]+d[k][j]; pos[i][j]=k; } } if(res==INF) puts("No solution."); else { for(int i=0;i<cnt;i++) cout<<path[i]<<" "; } return 0; } 

4.牛站（快速幂求n次方+用map离散化）

345. 牛站 - AcWing题库

d[ k, i , j ]表示从 i 到 j ，恰好经过k条边的最短路径

d[ a+b , i , j ] =min( d[a , i, k ] + d[ b, k, j ] ) k= 1 ~ n

用快速幂优化 k= 1 ~ n

时间复杂度O(logN*n^3)

牛逼的题解

AcWing 345. 牛站(通俗图解版) - AcWing


 

讯享网#include <bits/stdc++.h> using namespace std; const int N=210; int n,m; int S,E; int k; int g[N][N]; int res[N][N]; void mul(int c[][N],int a[][N],int b[][N]) { static int tmp[N][N]; memset(tmp,0x3f,sizeof tmp); for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) tmp[i][j]=min(tmp[i][j],a[i][k]+b[k][j]); memcpy(c,tmp,sizeof tmp); } 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); mul(g,g,g); k>>=1; } } int main() { cin>>k>>m>>S>>E; map<int,int> ids; memset(g,0x3f,sizeof g); if(!ids.count(S)) ids[S]=++n; if(!ids.count(E)) ids[E]=++n; S=ids[S],E=ids[E]; while(m--) { int a,b,c; cin>>c>>a>>b; if(!ids.count(a)) ids[a]=++n; if(!ids.count(b)) ids[b]=++n; a=ids[a],b=ids[b]; g[a][b]=g[b][a]=min(g[a][b],c); } qmi(); cout<<res[S][E]<<endl; return 0; }