首页 > 代码库 > hdu--1224--spfa||dp

hdu--1224--spfa||dp

2024-07-14 21:08:41   226人阅读

好久不写spfa了 但在纸上写写 还是可以敲出来 它的思想还是还是很简单 这里就不介绍了 掌握spfa真的很好 除非题目的数据故意卡spfa...那就只能用dij去做了或者floyd

这题 相比一般我们去求 最短路 有稍许不同 但是你只要明白了spfa的思想 就是进行下转换就可以了

又是打印路径 好多题遇到了啊.. 我还是喜欢用stack去打印 虽然这样会显得多一步for的入栈 但这样只有O(n) 如果tle 肯定也与此无关吧-

这里 我的建图 就是一般的使用struct的邻接表 本来想写下 前向星的 发现对于head数组 有点生疏了 就不写了 还是我现在写的这个容易理解 你可以将它看成自己模拟了个vector来实现 很像的

　　　　　　touch   me

  1 #include <iostream>  2 #include <cstring>  3 #include <queue>  4 #include <stack>  5 using namespace std;  6   7 int n;  8 const int size = 110;  9 struct graph 10 { 11     int num; 12     int next[size-10]; 13 }node[size]; 14 int val[size]; 15 int sum[size]; 16 int path[size]; 17 bool vis[size]; 18 queue<int>q; 19 stack<int>s; 20  21 void init( ) 22 { 23     while( !q.empty() ) 24         q.pop(); 25     for( int i = 0 ; i<size-5 ; i++ ) 26         node[i].num = 0; 27     memset( vis , false , sizeof(vis) ); 28     memset( sum , 0 , sizeof(sum) ); 29     memset( path , -1 , sizeof(path) ); 30 } 31  32 void spfa( ) 33 { 34     int now , point; 35     q.push(1); 36     vis[1] = true; 37     while( !q.empty() ) 38     { 39         now = q.front(); 40         q.pop(); 41         for( int i = 0 ; i<node[now].num ; i++ ) 42         { 43             point = node[now].next[i]; 44             if( sum[now] + val[point] >= sum[point] ) 45             { 46                 sum[point] = sum[now] + val[point]; 47                 path[point] = now; 48                 if( !vis[point] ) 49                 { 50                     vis[point] = true; 51                     q.push(point); 52                 } 53             } 54         } 55         vis[now] = false; 56     } 57 } 58  59 void output( ) 60 { 61     s.push( n+1 ); 62     for( int i = path[n+1] ; i!=-1 ; i=path[i] ) 63     { 64         s.push( i ); 65     } 66     while( !s.empty( ) ) 67     { 68         if( s.top() == n+1 ) 69         { 70             cout << 1; 71         } 72         else 73         { 74             cout << s.top( ) << "->"; 75         } 76         s.pop(); 77     } 78     cout << endl; 79 } 80  81 int main() 82 { 83     int t , m , cnt , x , y , num; 84     while( cin >> t ) 85     { 86         cnt = 1; 87         for( int k = 1 ; k<=t ; k++ ) 88         { 89             init(); 90             cin >> n; // n+1个结点 91             for( int i = 1 ; i<=n ; i++ ) 92             { 93                 cin >> val[i]; 94             } 95             val[n+1] = 0; 96             cin >> m; 97             while( m-- ) // m对关系 98             { 99                 cin >> x >> y;100                 num = node[x].num;101                 node[x].next[ node[x].num++ ] = y;102             }103             spfa();104             cout << "CASE " << cnt++ << "#" << endl;105             cout << "points " << ": " << sum[n+1] << endl;106             cout << "circuit : ";107             output( );108             if(k<t)109                 cout << endl;110         }111     }112     return 0;113 }
View Code

这几天 正好不出去玩 看了好多部电影--推荐几部--意外 -古天乐  单身男女--古天乐 窃听风云 1 2 3 大概就看了这5部吧

写完这个去看下 孤男寡女--刘德华  然后晚上来写下它的dp版本=-=

 


联系
我们