poj 1125 Floyd简单

叁歲伎倆 2021-11-29 17:36 221阅读 0赞

这是求所有节点间最短路径的题。果断用floyd，三个for循环就OK！如果不懂floyd，[请看这里][Link 1]。题意有点绕。。。我不知道怎么描述，看了discuss里面有个人的解释，非常好。请看下面：

释疑：  
\- 一个人可以同时给几个人发送消息  
\- 结束状态必须是所有人都受到了消息  
  
思路：  
1. 通过Stockbrokers(SB？）i发消息，所有人同时收到所花时间 （可以是无穷哦~）  
2. 找出第一步所得结果中的值最小的那一个  
3. 如果第二步所得结果为无穷，说明此图不可联通~

![2012042411513865.png][]

#include <iostream>
    #include <fstream>
    
    using namespace std;
    #define INF 10000
    #define LEN 105
    #define MAX(a,b) (a>b?a:b)
    
    int path[LEN][LEN];
    int map[LEN][LEN];
    int n,maxcost,maxid;
    
    void Floyd()
    {
        int k,i,j;
    /*    for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
                    path[i][j]=i;
        }
    */
        for(k=1; k<=n; k++)
        {
            for(i=1; i<=n; i++)
            {
                for(j=1; j<=n; j++)
                {
                    if(i!=j && map[i][j]>map[i][k]+map[k][j])  //不用求i->i
                    {
                        map[i][j]=map[i][k]+map[k][j];
                        path[i][j]=path[k][j];
                    }
                }
            }
        }
    }
    
    void GetResult()
    {
        int i,j;
        bool flag;
        maxcost=INF;
        for(i=1; i<=n; i++)
        {
            int tem_max=0;
            flag=true;
            for(j=1; j<=n; j++)  //寻找i到其它节点的最短路径中的最大者
            {
                if(map[i][j]==INF)  //i->j不能到达
                {
                    if(i==j)  //i->i  不计算
                        continue;
                    else
                    {
                         flag=false;
                         break;
                    }
                }
                else
                {
                     tem_max=MAX(map[i][j],tem_max);
                }
            }
            if(flag==false)
                continue;
            else if(tem_max<maxcost)  //寻找最小
            {
                maxcost=tem_max;
                maxid=i;
            }
        }
    }
    
    int main()
    {
        int i,j;
        freopen("acm.txt","r",stdin);
        while(scanf("%d",&n)!=EOF && n)
        {
            for(i=0; i<=n; i++)
            {
                for(j=0; j<=n; j++)
                {    
                    map[i][j]=INF;  //表示不能到达
                }
            }
            int m,to,co;  
            for(i=1; i<=n; i++)
            {
                scanf("%d",&m);
                for(j=1; j<=m; j++)
                {
                    scanf("%d%d",&to,&co);
                    map[i][to]=co;
                }
            }
            Floyd();
            GetResult();
            if(maxcost==INF)
                printf("disjoint\n");
            else
                printf("%d %d\n",maxid,maxcost);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Jason-Damon/archive/2012/04/24/2467773.html

[Link 1]: http://www.cnblogs.com/twjcnblog/archive/2011/09/07/2170306.html
[2012042411513865.png]: /images/20211129/74ec8e202a3a40f9ace0b207ca78bf19.png