首页 > 代码库 > hdu--1285 && 4857 --正向 || 逆向拓扑排序 && 优先队列

hdu--1285 && 4857 --正向 || 逆向拓扑排序 && 优先队列

2024-07-17 00:20:26   223人阅读

头太晕了 喝了太多 ..

就想提一点 对于 拓扑排序的这2题 为什么一个是正向 一个是逆向

主要是看题目要求  因为拓扑排序的结果总是有很多种存在的

一般来说 它会让你输出它指定要求的形式的答案

那么 如果是按字典序输出 就是 greater<int> 情况下的优先队列 并且 正向

　　如果是尽量使小的数字 靠前输出 而不是追求 字典序 可以考虑 逆向拓扑 逆向输出 

但 这些都不是唯一的 一定要分析好题目

曾经 看过一个讲动态规划的word  说拓扑是为DP作准备的 似乎有点道理

这两题 代码 实在太相像了 我都嫌丢人了..........

 1 //正向拓扑排序 2 #include <iostream> 3 #include <cstring> 4 #include <vector> 5 #include <queue> 6 using namespace std; 7  8 int n; 9 const int size = 520;10 vector<int>ve[size];11 priority_queue<int,vector<int>,greater<int> >q;12 int in[size];13 int arr[size];14 15 void init( )16 {17     for( int i = 0 ; i<size; i++ )18     {19         in[i] = 0;20         ve[i].clear();21     }22 }23 24 void topo( )25 {26     int cnt = 0 , now , u;27     for( int i = 1 ; i<=n ; i++ )28     {29         if( in[i] == 0 )30         {31             q.push(i);32         }33     }34     while( !q.empty() )35     {36         now = q.top();37         q.pop();38         arr[cnt++] = now;39         for( int i = 0 ; i<ve[now].size() ; i++ )40         {41             u = ve[now][i];42             in[u] --;43             if( in[u] == 0 )44             {45                 q.push(u);46             }47         }48     }49     for( int i = 0 ; i<cnt-1 ; i++ )50     {51         cout << arr[i] << " ";52     }53     cout << arr[cnt-1] << endl;54 }55 56 int main()57 {58     cin.sync_with_stdio(false);59     int m , x , y;60     while( cin >> n >> m )61     {62         init();63         while( m-- )64         {65             cin >> x >> y;66             ve[x].push_back(y);67             in[y] ++;68         }69         topo();70     }71     return 0;72 }
View Code

 

 

 1 //逆向拓扑排序 2 #include <iostream> 3 #include <cstring> 4 #include <queue> 5 #include <vector> 6 using namespace std; 7  8 int n; 9 const int size = 30010;10 int in[size];11 int arr[size];12 vector<int>ve[size];13 priority_queue<int,vector<int>,less<int> >q;14 15 void init( )16 {17     for( int i = 1 ; i<=n ; i++ )18     {19         ve[i].clear();20         in[i] = 0;21     }22 }23 24 void topo( )25 {26     int cnt = 0;27     for( int i = 1 ; i<=n ; i++ )28     {29         if( in[i] == 0 )30         {31             q.push(i);32         }33     }34     while( !q.empty() )35     {36         int now = q.top();37         q.pop();38         arr[cnt++] = now;39         for( int i = 0 ; i<ve[now].size() ; i++ )40         {41             int u = ve[now][i];42             in[u] --;43             if( in[u] == 0 )44             {45                 q.push(u);46             }47         }48     }49     for( int i = cnt-1 ; i>=1 ; i-- )50     {51         cout << arr[i] << " ";52     }53     cout << arr[0] << endl;54 }55 56 int main()57 {58     cin.sync_with_stdio(false);59     int t , m , x , y;60     cin >> t;61     while( t-- )62     {63         cin >> n >> m;64         init( );65         while( m-- )66         {67             cin >> x >> y;68             in[x] ++;69             ve[y].push_back(x);70         }71         topo();72     }73     return 0;74 }
View Code

 

 

today:

　　一年之前 我喝醉了 你陪我去南湖边吹风

　　一年之后 我喝醉了 我陪他们去ktv .....　　

 


联系
我们