Floyd算法的应用

简介: Floyd算法的应用

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.牛的旅行(最短路

1125. 牛的旅行 - AcWing题库

#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.排序(传递闭包)

343. 排序 - AcWing题库

#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.观光之旅(找最小环)

344. 观光之旅 - AcWing题库

每次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离散化)

345. 牛站 - AcWing题库

离散数学的图论中经过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;
}
目录
打赏
0
0
0
0
2
分享
相关文章
员工上网行为监控中的Go语言算法:布隆过滤器的应用
在信息化高速发展的时代,企业上网行为监管至关重要。布隆过滤器作为一种高效、节省空间的概率性数据结构,适用于大规模URL查询与匹配,是实现精准上网行为管理的理想选择。本文探讨了布隆过滤器的原理及其优缺点,并展示了如何使用Go语言实现该算法,以提升企业网络管理效率和安全性。尽管存在误报等局限性,但合理配置下,布隆过滤器为企业提供了经济有效的解决方案。
99 8
员工上网行为监控中的Go语言算法:布隆过滤器的应用
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
87 3
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
36 12
基于 Python 的布隆过滤器算法在内网行为管理中的应用探究
在复杂多变的网络环境中,内网行为管理至关重要。本文介绍布隆过滤器(Bloom Filter),一种高效的空间节省型概率数据结构,用于判断元素是否存在于集合中。通过多个哈希函数映射到位数组,实现快速访问控制。Python代码示例展示了如何构建和使用布隆过滤器,有效提升企业内网安全性和资源管理效率。
36 9
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
【狂热算法篇】探秘图论之 Floyd 算法:解锁最短路径的神秘密码(通俗易懂版)
解锁机器学习的新维度:元学习的算法与应用探秘
元学习作为一个重要的研究领域,正逐渐在多个应用领域展现其潜力。通过理解和应用元学习的基本算法,研究者可以更好地解决在样本不足或任务快速变化的情况下的学习问题。随着研究的深入,元学习有望在人工智能的未来发展中发挥更大的作用。
探索企业文件管理软件:Python中的哈希表算法应用
企业文件管理软件依赖哈希表实现高效的数据管理和安全保障。哈希表通过键值映射,提供平均O(1)时间复杂度的快速访问,适用于海量文件处理。在Python中,字典类型基于哈希表实现,可用于管理文件元数据、缓存机制、版本控制及快速搜索等功能,极大提升工作效率和数据安全性。
77 0
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
82 1
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
101 1

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等