•  
  • 数据结构和算法
  • POJ 3660 && NYIST 211 Cow Contest && ZOJ 1060 Sorting It All Out【Floyd算法扩展应用】

POJ 3660 && NYIST 211 Cow Contest && ZOJ 1060 Sorting It All Out【Floyd算法扩展应用】

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 03 月 30 日

Floyd算法:

Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法(百度百科给的。。。)。

核心思路

通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

从图的带权邻接矩阵A=[a(i,j)] n×n开始,递归地进行n次更新,即由矩阵D(0)=A,按一个公式,构造出矩阵D(1);又用同样地公式由D(1)构造出D(2);……;最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度,称D(n)为图的距离矩阵,同时还可引入一个后继节点矩阵path来记录两点间的最短路径。

采用的是松弛技术,对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);(由此可见Floyd算法不适合大规模数据、稀疏矩阵处理,比较适合小规模密集矩阵类的题目)

其状态转移方程如下: map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}

map[i,j]表示i到j的最短距离

K是穷举i,j的断点

map[n,n]初值应该为0,或者按照题目意思来做。

当然,如果这条路没有通的话,还必须特殊处理,比如没有map[i,k]这条路

Floyd作为最短路算法众所周知,但是还有一些扩展性应用,比如可以根据元素间的某种关系建图,对图中的各个元素间的关系进行一个关系传递闭包。

下边给出两个扩展实例:

POJ 3660  &&NYIST 211 Cow Contest:(代码十分短,简单易懂,就不解释了)

#include <cstdio>  
#include <cstring>  
using namespace std;  
bool cows[101][101];  
void Floyd(const int &n)  
{  
    for (int k=1;k<=n;k++)  
        for(int i=1;i<=n;i++)  
            for (int j=1;j<=n;j++)  
            {  
                cows[i][j]= cows[i][j] || (cows[i][k] &&cows[k][j]);  
            }  
}  
int main()  
{  
    //freopen("1.txt","r",stdin);  
    int n,m,t1,t2;  
    while(~scanf("%d%d",&n,&m) && n && m)  
    {  
        memset(cows,0,sizeof(cows));  
        for (int i=0;i<m;i++)  
        {  
            scanf("%d%d",&t1,&t2);  
            cows[t1][t2]=1;  
        }  
        Floyd(n);  
        t2=0;  
        for (int i=1;i<=n;i++)  
        {  
            t1=0;  
            for (int j=1;j<=n;j++)  
            {  
                if(cows[i][j] || cows[j][i]) t1++;  
            }  
            if(t1==(n-1)) t2++;  
        }  
        printf("%d\n",t2);  
    }  
}  

ZOJ 1060 Sorting It All Out:

最后排序输出之后还有一个".",汗死!!!

题解: n个元素要是能确定一个全序,任意两个元素间必能比较大小,这样关系总数应该有n-1 + n-2 + n-3 + …+1 = n*(n-1)/2 个。

如果中途达到这个关系总数,则Sorted sequence determined after xxx relations: yyy...y.

每次输入数据后进行Floyd关系传递,如果出现矛盾关系则:Inconsistency found after xxx relations.

如果数据输完关系数扔未达到总关系数的则:Sorted sequence cannot be determined.

#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
bool relations[27][27],flag1,flag2;  
struct data{char ch;int num;} datas[27];  
int rightnum;  
void Floyd(const int &n){  
    for (int k=1;k<=n;k++)  
        for(int i=1;i<=n;i++)  
            for (int j=1;j<=n;j++)  
                relations[i][j]=relations[i][j] ||(relations[i][k] &&relations[k][j]);  
}  
void check(int n){  
    rightnum=0;  
    for (int i=1;i<=n;i++)  
        for (int j=1;j<=n;j++)  
            if(relations[i][j] && relations[j][i])   
            {flag1=1;return;}  
            else if(relations[i][j])  
                rightnum++;  
}  
bool cmp(data d1,data d2)  
{return d1.num>d2.num;}  
void sortData(int n){  
    int num;  
    for (int i=1;i<=n;i++){  
        num=0;  
        for (int j=1;j<=n;j++){  
            if(relations[i][j]) num++;  
        }  
        datas[i].num=num;  
    }  
    sort(datas,datas+n+1,cmp);  
}  
void init(){  
    memset(relations,0,sizeof(relations));  
    memset(datas,0,sizeof(datas));  
    flag1=0;flag2=0;  
    for (int i=0;i<26;i++)  
        datas[i+1].ch='A'+i;  
    datas[0].num=-1;  
}  
int main(){  
    freopen("1.txt","r",stdin);  
    int n,m,t1,t2;  
    char ch1,ch2,ch3;  
    while(~scanf("%d%d",&n,&m) && n && m){  
        init();  
        getchar();  
        for (int i=0;i<m;i++){  
            scanf("%c%c%c",&ch1,&ch3,&ch2);  
            getchar();  
            if(flag1 || flag2) continue;  
            t1=(int)(ch1-'A'+1);  
            t2=(int)(ch2-'A'+1);  
            relations[t1][t2]=1;  
            Floyd(n);  
            check(n);  
            if(flag1){  
                printf("Inconsistency found after %d relations.\n",i+1);  
                continue;  
            }  
            if(rightnum==n*(n-1)/2){   
                flag2=1;   
                printf("Sorted sequence determined after %d relations: ",i+1);  
                sortData(n);  
                for (int i=0;i<n;i++)  
                    printf("%c",datas[i].ch);  
                printf(".\n");  
                continue;  
            }  
        }  
        if(!(flag1 || flag2))  
            printf("Sorted sequence cannot be determined.\n");  
    }  
} 

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

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

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日