简单的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=0,k=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*k;
}//快读
int main() {
    
    n=read(),m=read(),s=read();
    for(int i = 1; i <= n; i++) {
        for(int j = 1;j <= n; j++) {
            dis[i][j] = INF;//先初始化为正无穷 
        }
    }
    for(int i = 1, 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 = 1; k <= n; k++) {//k为中介点，就是一个DP 
        for(int i = 1; i <= n; i++) {//i为起点，j为终点 
        if(i == k || dis[i][k] == INF) continue;
            for(int j = 1;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] = 0;
    for(int i = 1; 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 = 25 + 9;

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==0 && m==0) break;//用0表示退出标志 
        name.clear();//初始化
        num.clear(); 
        memset(d,0,sizeof(d));//初始化
        //多数据输入的题目 每次清空是个好习惯 
        if(tmp != 1) printf("
"); 
        printf("Calling circles for data set %d:
",tmp);//题目需要 
//        for(int i = 1; i <= n; i++) d[i][i] = 0;//也可以不写，这就是那么个意思，自己不能给自己打电话

        string s1,s2;
        int number = 0; //真正申请编号用的 
        for(int i = 1; i <= m; i++) {
            int x = i*2-1, y = i*2;//错了啦！！（本人一开始以为这是申请编号...）
            //谁知道它可能重复输入某些人的名字，如果直接写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]]  = 1;//联通 
            //吐槽一句：我想num的使命就是这了（方便保存编号，以便后面把编号换成人名 和 联通）... 
        }
        
        for(int k = 1; k <= n; k++) {//求有向图的传递闭包 
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    d[i][j] = d[i][j] || (d[i][k] && d[k][j]);
                }
            }
        }
        
        memset(in,0,sizeof(in));
        for(int i = 1; i <= n; i++) {//寻找联通的圈，并输出解 
            if(!in[i]) {
                cout << name[i] ;
                in[i] = 1;
                for(int j = 1; j <= n; j++) {
                    if(d[i][j]==1 && d[j][i]==1 && !in[j]) {//只有当i 与 j互相打电话时（表示联通）才输出 
                        cout <<", "<<name[j];
                        in[j] = 1; 
                    }
                }
                printf("
");
            }
        }
    }
    return 0; 
}

最小环：

参考博客：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 = 99999999;//切记别爆  inf*3即可//程序可能出现3个inf相加
const int MAX = 100+9;

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 = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == j) e[i][i] = dis[i][i] = 0;
                else e[i][j] = dis[i][j] = INF;
            }
        }
        int a,b,c;
        for(int i = 1; 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 = 1; 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 = 1; 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+1; j < k; j++) {
                    /*j从i+1开始是因为无向图的对称性质 ？？？
                    */ 
                    ans = min(ans , dis[i][j] + e[i][k] + e[k][j]);
                }
            }
            
            for(int i = 1; i <= n; i++) {//松弛操作 更新最短路 
                for(int j = 1;  j <= n; j++) {
                    dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
                }
            }
        }
        if(ans == INF) printf("It's impossible.
");
        else printf("%d
",ans);
    }
    return 0;
    
}

这个环为：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 = 200+9;
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 = 1; i <= n; i++) {
        scanf("%d",&w[i]);
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            e[i][j] = INF;
        }
    }//貌似这题不用这个也行 
    int a,b,c;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d%d",&a,&b,&c);
        e[a][b] = min(e[a][b],c+w[a]); 
    }
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; 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[1][1]==INF?-1:e[1][1]); 
    return 0;
}

其他运用：

一个小运用：

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 = 1, x, y; i <= m; i++) {
        scanf("%d%d",&x,&y);
        a[x][y] = 1;
        b[x]++,c[y]++;
    }
    for(int k = 1; k <= n; k++) {//用floyd枚举中间点 
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(a[i][j] == 0 && (a[i][k] == 1) && (a[k][j] == 1) ) {
                // 如果 i 比 k 厉害，k 比 j 厉害， i 自然 比 j 厉害 
                //当 i 和 j 没有 比过赛&& i 比 j厉害，通过枚举中间点，可以确定这个中间点k的b[k],c[k] 
                    a[i][j] = 1;
                    b[i]++;
                    c[j]++;
                }
            }
        }
    } 
    for(int i = 1; i <= n; i++) if(b[i] + c[i] == n - 1) ans++;
    printf("%d",ans);
}

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

此题 还行