首页 > 代码库 > hdu--1599--最小环<会加深你对floyd的理解>
hdu--1599--最小环<会加深你对floyd的理解>
自己好懒那....
这题的主要知识点 应该是 对最小环的运用了
这里的图 是无向图
无向图的最小环至少有3个顶点
有向图的最小环至少有2个顶点
这边的做法是用floyd的思想去做
我们都知道起初我们用floyd来做的时候都是直接
for k -> 1 to n
for i -> 1 to n
for j -> 1 to n
这边 有一点很重要的 不知道当时你学的时候也没有留意到 当你循环到k的时候 此时我们已经求得 图中所有顶点之间靠顶点编号0,1,2,……k-1联通的最短路
因为该最小环 至少有3个顶点 那么我们任意取这3个紧密连接在一起的三点 假如有这样的吧 a-b-c-i-k-j-d-e-a 那么我们的做法就是mp[i][k]+mp[k][j]+dist[i][j]
dist[i][j]就是 i <-> j之间循环到k的时候以最大k-1联通的最短路
**********
应该用spfa dij都是可以同样可以求出值的吧
也可以去写下 试试
**********
这题 我被深深地坑惨了....0x3f3f3f3f溢出了 orz
一般 都是只会 mp[i][k] + mp[k][j]这样就不会溢出
但是这边会有 dist[i][j] + mp[i][k]+ mp[k][j] 这样一来 就要溢出 当全部都是0x3f3f3f3f的时候
1 #include <iostream> 2 using namespace std; 3 4 int n; 5 const int size = 110; 6 const int inf = 888888; 7 int mp[size][size]; 8 int dist[size][size]; 9 10 int floyd( )11 {12 int val;13 int ans = inf;14 for( int k = 1 ; k<=n ; k++ )15 {16 for( int i = 1 ; i<k ; i++ )17 {18 for( int j = i+1 ; j<k ; j++ )19 {20 val = dist[i][j] + mp[i][k] + mp[k][j];21 if( val < ans )22 {23 ans = val;24 }25 }26 }27 for( int i = 1 ; i<=n ; i++ )28 {29 for( int j = 1 ; j<=n ; j++ )30 {31 if( dist[i][j] > dist[i][k] + dist[k][j] )32 {33 dist[i][j] = dist[i][k] + dist[k][j];34 }35 }36 }37 }38 return ans;39 }40 41 int main()42 {43 int m , ans , from , to , len;44 while( cin >> n >> m )45 {46 for( int i = 1 ; i<=n ; i++ )47 {48 for( int j = 1 ; j<=n ; j++ )49 {50 mp[i][j] = inf;51 }52 }53 while( m-- )54 {55 cin >> from >> to >> len;56 mp[from][to] = mp[from][to] > len ? len : mp[from][to];57 mp[to][from] = mp[from][to];58 }59 for( int i = 1 ; i<=n ; i++ )60 {61 for( int j = 1 ; j<=n ; j++ )62 {63 dist[i][j] = mp[i][j];64 }65 }66 ans = floyd( );67 if( ans == inf )68 cout << "It‘s impossible." << endl;69 else70 cout << ans << endl;71 }72 return 0;73 }
你只要在floyd里面 再添加个path数组 可以自己在试着打印路径
today:
当我沉默地面对你
你又怎么知道在我心里对你说了多少遍
当我一成不变地站在你面前
你又怎么知道我内心早已为你百转千回
hdu--1599--最小环<会加深你对floyd的理解>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。