简单的floyd—

前言：

（摘自https://www.cnblogs.com/aininot260/p/9388103.html）：

在最短路问题中，如果我们面对的是稠密图（十分稠密的那种，比如说全连接图），计算多源最短路的时候，Floyd算法才能充分发挥它的优势，彻彻底底打败SPFA和Dijkstra

在别的最短路问题中都不推荐使用这个算法

功能：求最短路径，求有向图的最小环或者最大环（顶点数>=2），求无向图的最小环（顶点数>=3）。

最短路径

//code by virtualtan 2019/2

 #include<cstdio>

 #include<iostream>

 #define INF 200000000

 #define MAX 10001

 int n,m,s;

 int dis[MAX][MAX];

 inline int read()

 {

     int x=,k=; char c=getchar();

     while(c<''||c>''){if(c=='-')k=-;c=getchar();}

     while(c>=''&&c<='')x=(x<<)+(x<<)+(c^),c=getchar();

     return x*k;

 }//快读

 int main() {

     n=read(),m=read(),s=read();

     for(int i = ; i <= n; i++) {

         for(int j = ;j <= n; j++) {

             dis[i][j] = INF;//先初始化为正无穷

         }

     }

     for(int i = , x, y, val; i <= m; i++) {

         scanf("%d%d%d",&x,&y,&val);

         dis[x][y] = std::min(dis[x][y], val);//如果有边相连 //可以解决重边

     }//用邻接矩阵存图

     for(int k = ; k <= n; k++) {//k为中介点，就是一个DP

         for(int i = ; i <= n; i++) {//i为起点，j为终点

         if(i == k || dis[i][k] == INF) continue;

             for(int j = ;j <= n; j++) {

                 if(dis[i][j] > dis[i][k] + dis[k][j])

                     dis[i][j] = dis[i][k] + dis[k][j];

             }

         }

     }

     dis[s][s] = ;

     for(int i = ; i <= n; i++)

     if(i != s)    printf("%d ",dis[s][i]);

     else printf("0 ");

 }

注：判断负环：如果存在u，使dis[u][u] < 0; 则存在负环

//参考代码&blog（实际上是比我写的好的多的东西）
https://ksmeow.moe/floyd_warshall/

注意：

dis[i][j]实际上是dis[k][i][j]，表示i到j的中间节点（不包括i，j）都在（1，k）时，i到j的最短路
而又因为每一层都是有上一层决定，不会受这一层影响，所以可以利用滚动数组优化内存空间，将k去除掉

打印路径：

传送

传递闭包

在有向图中，有时不用关心路径的长度，而只关心两点间是否有通路，则可以用“1” 表示联通， “0”表示不联通，这样预处理少许修改后，再把主程序中改成

d[i][j] = d[i][j] || (d[i][k] && d[i][k]);

这样的结果称为有向图的传递闭包

运用例题：https://vjudge.net/problem/UVA-247

 #include<bits/stdc++.h>

 #include<map>

 using namespace std;

 const int MAX =  + ;

 int n,m,tmp;

 bool d[MAX][MAX];

 map <string ,int> num;//人名代表的编号

 map <int , string > name;//根据编号取人名：用于输出答案

 bool in[MAX];//用于防止联通分量中的人重输出 

 int main() {

     while(++tmp) {//换行专用

         scanf("%d%d",&n,&m);

         if(n== && m==) break;//用0表示退出标志

         name.clear();//初始化

         num.clear();

         memset(d,,sizeof(d));//初始化

         //多数据输入的题目 每次清空是个好习惯

         if(tmp != ) printf("\n");

         printf("Calling circles for data set %d:\n",tmp);//题目需要

 //        for(int i = 1; i <= n; i++) d[i][i] = 0;//也可以不写，这就是那么个意思，自己不能给自己打电话

         string s1,s2;

         int number = ; //真正申请编号用的

         for(int i = ; i <= m; i++) {

             int x = i*-, y = i*;//错了啦！！（本人一开始以为这是申请编号...）

             //谁知道它可能重复输入某些人的名字，如果直接写num[s1]=x,num[s2]=y会导致先前名字的编号被修改，这是不符合题意的

             cin >> s1 >> s2;

             if(!num.count(s1)) num[s1] = ++number;

             if(!num.count(s2)) num[s2] = ++number;

             name[ num[s1] ] = s1; name[ num[s2] ] = s2;

             d[num[s1]][num[s2]]  = ;//联通

             //吐槽一句：我想num的使命就是这了（方便保存编号，以便后面把编号换成人名 和 联通）...

         }

         for(int k = ; k <= n; k++) {//求有向图的传递闭包

             for(int i = ; i <= n; i++) {

                 for(int j = ; j <= n; j++) {

                     d[i][j] = d[i][j] || (d[i][k] && d[k][j]);

                 }

             }

         }

         memset(in,,sizeof(in));

         for(int i = ; i <= n; i++) {//寻找联通的圈，并输出解

             if(!in[i]) {

                 cout << name[i] ;

                 in[i] = ;

                 for(int j = ; j <= n; j++) {

                     if(d[i][j]== && d[j][i]== && !in[j]) {//只有当i 与 j互相打电话时（表示联通）才输出

                         cout <<", "<<name[j];

                         in[j] = ;

                     }

                 }

                 printf("\n");

             }

         }

     }

     return ;

 }

最小环：

参考博客：https://blog.csdn.net/qq_36386435/article/details/77403223

　　　　 https://www.cnblogs.com/zzqc/p/6855913.html

　　　　 https://blog.csdn.net/yo_bc/article/details/75042688

无向图的最小环：

（最大环略......）

板子：传送门

 #include<bits/stdc++.h>

 using namespace std;

 const int INF = ;//切记别爆  inf*3即可//程序可能出现3个inf相加

 const int MAX = +;

 int n,m;

 int dis[MAX][MAX];

 int e[MAX][MAX];

 int main() {

     while(cin>>n>>m) {//吐槽一下：杭电的OJ这里要写while(~scanf("%d%d",&n，&m) )

         for(int i = ; i <= n; i++) {

             for(int j = ; j <= n; j++) {

                 if(i == j) e[i][i] = dis[i][i] = ;

                 else e[i][j] = dis[i][j] = INF;

             }

         }

         int a,b,c;

         for(int i = ; i <= m; i++) {

             scanf("%d%d%d",&a,&b,&c);

             if(c < e[a][b]) //有可能重复输入某些边，但它权值又不一样

             e[a][b]=e[b][a] = dis[a][b]=dis[b][a] = c;

             //多一个 e数组 的作用在于此: 在松弛的过程中，会破坏掉两点之间是否真的存在边的表示，所有需要多开一个 e

             //没有真的存在边的话，e就会是INF

         }

         int ans = INF;

         /* 外层循环 k 用于更新最小环ans */

         for(int k = ; k <= n; k++) {

             /* 先判断最小环（也就是第一个for），再更新最短路（第二个for）的原因：

             会出现重边现象，所以一个环至少有三个点，所以每次先判最小环

             因为k必须是未用过的，此时的dis[i][j]是遍历了k-1次的最短路，用完判断了再去更新k对应的最短路。

             每次比较dist[i][j]+ e[i][k]+e[k][j]的最小值。k—>i———>j—>k;这样一直保证环是三个点。？？？

             */

             for(int i = ; i < k; i++) {//关于这里的"i<k"和下面的"j<k" ，我还看到了另一种写法“i<n,j<n”

             //原因不知道是不是这个（希望有人可以指点指点）：

             /* i循环到k-1的原因：

             举例：1->3 ,3->2（只有两条边） 的一个图

             已经用3把dis[1][2]给松弛了，再利用3来求最小环时，算出的ans=dis[1][2]+e[1][3]+e[3][2]

             这显然不是一个环...所以我们第一个for里i，j都是只循环到k-1

             这就是重边 ？？？

             */

                 for(int j  = i+; j < k; j++) {

                     /*j从i+1开始是因为无向图的对称性质 ？？？

                     */

                     ans = min(ans , dis[i][j] + e[i][k] + e[k][j]);

                 }

             }

             for(int i = ; i <= n; i++) {//松弛操作 更新最短路

                 for(int j = ;  j <= n; j++) {

                     dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);

                 }

             }

         }

         if(ans == INF) printf("It's impossible.\n");

         else printf("%d\n",ans);

     }

     return ;

 }

这个环为：j,k,i...j

有向图的最小环：

对于上面代码第43行部分，这个j之所以从i+1开始就可以了是因为无向图的对称性质，而有向图并不具有这个性质，所以需要改动.

仔细想一想，有向图的最小环其实只要直接跑一遍floyd，然后遍历一遍寻找最小的dis[i][i]即可（所以连dis[i][i] 一起都要初始化为INF哦），因为图是无向的所以不必担心出现重边啊

例题：传送门

 #include<bits/stdc++.h>

 using namespace std;

 const int MAX = +;

 const int INF = 0x3f3f3f3f;

 int n,m;

 int w[MAX];//w[i]表示弯道i的时间

 int e[MAX][MAX]; /*e[i][j]表示 弯道i到弯道j的最小直道时间 与 起点i的时间和

  这样就转化为一个普通的图了（节点无权值）*/

 int main() {

     scanf("%d%d",&n,&m);

     for(int i = ; i <= n; i++) {

         scanf("%d",&w[i]);

     }

     for(int i = ; i <= n; i++) {

         for(int j = ; j <= n; j++) {

             e[i][j] = INF;

         }

     }//貌似这题不用这个也行

     int a,b,c;

     for(int i = ; i <= m; i++) {

         scanf("%d%d%d",&a,&b,&c);

         e[a][b] = min(e[a][b],c+w[a]);

     }

     for(int k = ; k <= n; k++) {

         for(int i = ; i <= n; i++) {

             for(int j = ; j <= n; j++) {

                 e[i][j] = min(e[i][j],e[i][k]+e[k][j]);

             }

         }

     }

 //    int ans = INF;

 //    for(int i = 1; i <= n; i++) ans = min(ans,e[i][i]) ;

 //    if(ans==INF) ans = -1 ; //题目要求：必须经过1号弯道

     printf("%d",e[][]==INF?-:e[][]);

     return ;

 }

其他运用：

一个小运用：

POJ3660 Cow Conte http://poj.org/problem?id=3660

 #include<cstdio>

 //题目分析：如果 奶牛能力确定，则赢它的奶牛数 + 输给它奶牛数 == n - 1

 #define MAX 5555

 bool a[MAX][MAX];

 //a[x][y] == 1 表示 x 与 y 比赛，x胜

 int b[MAX], c[MAX];

 //c[i]  表示第i个奶牛赢过的奶牛数 ， b[j] 表示输的

 int n,m,ans;

 int main() {

     scanf("%d%d",&n,&m);

     //初始化

     for(int i = , x, y; i <= m; i++) {

         scanf("%d%d",&x,&y);

         a[x][y] = ;

         b[x]++,c[y]++;

     }

     for(int k = ; k <= n; k++) {//用floyd枚举中间点

         for(int i = ; i <= n; i++) {

             for(int j = ; j <= n; j++) {

                 if(a[i][j] ==  && (a[i][k] == ) && (a[k][j] == ) ) {

                 // 如果 i 比 k 厉害，k 比 j 厉害， i 自然 比 j 厉害

                 //当 i 和 j 没有 比过赛&& i 比 j厉害，通过枚举中间点，可以确定这个中间点k的b[k],c[k]

                     a[i][j] = ;

                     b[i]++;

                     c[j]++;

                 }

             }

         }

     }

     for(int i = ; i <= n; i++) if(b[i] + c[i] == n - ) ans++;

     printf("%d",ans);

 }

收获
floyd 可以确定两点之间的大小关系（通过枚举中间点）
不过要注意条件

此题还行

巴特西

简单的floyd——初学

前言：