Floyd算法的应用 – Zechel

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算法是用来求全源最短路,复杂度为n^3,但是如果通过选点来执行n此Dijkstra算法,可以在接近n^2longn的时间复杂度下完成全源最短路的求解,但是Floyd算法还具有一些应用的空间,比如求解传递闭包问题。

POJ1094

该题是为判断,给出的一系列二元关系中,判断是否能得到一个有序列,或者这些二元关系是矛盾的。在Floyd算法中,其实状态转移的方程就是一种关系的传递,即如果从i到k,再从k到j,那么必然能够从i到j,所以二者加起来就是一条从i到j的路径,值为其长度。所以同理也能够处理传递闭包的问题,只需要将关系式改为:

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

这样,如果d[i][j]的值为1,代表i和j存在这种关系,否则不存在。对于该题本身,需要运用二分法先判断在出现矛盾之前是否存在可推出的序列,如果没有则通过二分寻找是否存在矛盾的关系式,如果仍没有则代表关系式不足不能推出一个序列。在判断时,如果存在i和j使d[i][j]和d[j][i]同时为1,则说明存在矛盾,因为该关系单向的,如果使同时为0,则说明关系不清,因为不能确定二者顺序。还需要注意数据的初始化等等。

POJ1734

题目要求我们在无向图中寻找一个最小环,我们在Floyd算法的基础上,增加了一个新的式子:

d[i][j]+a[j][k]+a[k][i]

其中a数组为点和点之间距离的记录,d数组则是i到j的最短路径,所以该式子代表的是一个环,且起码具有i,j,k三个点,通过枚举变量,最后得到的该式子的最小值就是要求的答案。比较值得注意的是求取最小环的部分,用到了一个分治。代码如下:

#include<cstdio>
#include<vector>
#include<cstring>
#define maxn 305
using namespace std;
int a[maxn][maxn],d[maxn][maxn],pos[maxn][maxn];
int n,m,ans=0x3f3f3f3f;
vector<int>path;
void get_path(int x,int y)
{
    if(pos[x][y]==0)return ;
    get_path(x,pos[x][y]);
    path.push_back(pos[x][y]);
    get_path(pos[x][y],y);
}
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=n;i++)a[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        a[y][x]=a[x][y]=min(a[x][y],z);
    }
    memcpy(d,a,sizeof(a));
    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]+a[j][k]+a[k][i]<ans)
                {
                    ans=d[i][j]+a[j][k]+a[k][i];
                    path.clear();
                    path.push_back(i);
                    get_path(i,j);
                    path.push_back(j);
                    path.push_back(k);
                }
            }
        }
        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(ans==0x3f3f3f3f)
    {
        printf("No solution.");
    }
    else
    {
        for(int i=0;i<path.size();i++)
        {
            printf("%d ",path[i]);
        }
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

川公网安备 51130202000337号