Posted on 2010-08-27 04:01
acronix 阅读(114)
评论(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 == 0) break;
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;
}