posts - 64, comments - 4, trackbacks - 0, articles - 0

pku_1125(参考了 cdy20)

Posted on 2010-08-27 04:01 acronix 阅读(111) 评论(0)  编辑 收藏 引用 所属分类: qqy解题报告

/*
     Sourse: http://cdy20.bokee.com/viewdiary.41014871.html
  Name: Floyd-Warshall poj 1125
  Copyright: cdy20
  Author: cdy20
  Date: 29-07-08 16:38
  Description: Floyd-Warshall 复杂度O(n^3)
   本题目求那个中转者发信息给其他所有人 的时间最快
   特别注意:一个人发信息给其他人,最快完成这项工作所需的时间  
             由时间花费最长那个决定  
  总结:floyd其实都是根据那两个定理变化,虽然那两个定理比较傻b
  (一看就知道,刚开始还奇怪,一看就知道的定理有什么用,
  现在发现,sb的一看就知道的定理可以变化成一个算法,几个定理解决一个问题)
  
  定理(大概):
                1.任何两点i,j之间的路径若通过第三个点v,
                则此时i,v之间,v,j之间所连路径也是最短的.  
                a[i][j]最短-->a[i][v],a[v][j]最短  (v为最短路径i-j经过的点)
  
                2.若i,j之间的路径比i,v之间,v,j之间路径的和大则i,j之间最短路径不大于i,v之间,
                v,j之间路径的和.
                 a[i][j]=min(a[i][j],a[i][k] a[k][j]);(这是在程序过程中,不断更新的)  
  
*/

//考察点:  floyd
//思路: 利用floyd求出任意两点之间的最短时间(存放在数组a[i][j]中)   找出a[i][j]中的最大值就是通知所有人所需要的最短时间(a[i][j]中的某一个值代表通知某人需要的最短时间,因此任意两个人之间通知的最短时间已知  找到所有最短时间的最大值就是信息散布给所有人时的最坏情况 也就是说  当整个网络中最慢被通知到的人都被通知到了,有理由相信所有人都可以在这个时间内被通知到)  于是先用floyd求出任意两点之间的长度  然后找到最大值 如果找不到就输出 disjoint 
//提交情况: 1AC
主要是在设置maxint的时候出错了  原来(错误的状态是): const int INF = 1 << 30;  正确的设置方法应该是 const int INF = 0xfffffff;
//收获: 应用了一次floyd算法 初步熟悉了该算法 学会了怎么找到最小   学会了怎样写 "没有找到希望的值"
//经验:  写好代码以后要观察  时刻注意变量是不是需要初始化
//AC code
#include<stdio.h>
#include
<memory.h>
#include
<iostream>
#define MAX 101
using namespace std;
const int INF = 0xfffffff;
int a[101][101];

int main()
{
   
 int n,m,i,j,k;
    
int tmp,val;

    
while(1)
        {
            
for(i=1;i<=100;i++)
                           
for(j=1;j<=100;j++)
                                              a[i][j] 
= INF;
            scanf(
"%d",&n);
            
if(n == 0break;
            
for(i=1;i<=n;i++)
            {
                             a[i][i] 
= 0;
                             scanf(
"%d",&m);
                             
for(j=0;j<m;j++)
                             {
                                              scanf(
"%d%d",&tmp,&val);
                                              a[i][tmp] 
= val;
                             }
            }

            
for(k=1;k<=n;k++)
                             
for(i=1;i<=n;i++)
                                              
for(j=1;j<=n;j++)
                                              {
                                                   a[i][j] 
= min(a[i][j],a[i][k]+a[k][j]);
                                              }
            val 
= -1;
            
int ans = INF;
            
for(i=1;i<=n;i++)
            {
                             tmp 
= -1;
                             
for(j=1;j<=n;j++)
                             {
                                      tmp 
= max(tmp,a[i][j]);
                             }
                             
if(tmp < ans) {ans = tmp;val = i;}
            }
            
if(val == -1) printf("disjoint\n");
            
else printf("%d %d\n",val,ans);
    }
    
return 0;
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理