首页 > 代码库 > hdu 2647 Reward - 拓扑排序
hdu 2647 Reward - 拓扑排序
<style></style>
Dandelion‘s uncle is a boss of a factory. As the spring festival is coming , he wants to distribute rewards to his workers. Now he has a trouble about how to distribute the rewards.
The workers will compare their rewards ,and some one may have demands of the distributing of rewards ,just like a‘s reward should more than b‘s.Dandelion‘s unclue wants to fulfill all the demands, of course ,he wants to use the least money.Every work‘s reward will be at least 888 , because it‘s a lucky number.
The workers will compare their rewards ,and some one may have demands of the distributing of rewards ,just like a‘s reward should more than b‘s.Dandelion‘s unclue wants to fulfill all the demands, of course ,he wants to use the least money.Every work‘s reward will be at least 888 , because it‘s a lucky number.
Input
One line with two integers n and m ,stands for the number of works and the number of demands .(n<=10000,m<=20000)
then m lines ,each line contains two integers a and b ,stands for a‘s reward should be more than b‘s.
Output
For every case ,print the least money dandelion ‘s uncle needs to distribute .If it‘s impossible to fulfill all the works‘ demands ,print -1.
Sample Input
2 11 22 21 22 1
Sample Output
1777-1
反向建图，跑拓扑排序即可。
Code
1 /** 2 * hdu 3 * Problem#2647 4 * Accepted 5 * Time:31ms 6 * Memory:1976k 7 */ 8 #include <iostream> 9 #include <cstdio> 10 #include <ctime> 11 #include <cmath> 12 #include <cctype> 13 #include <cstring> 14 #include <cstdlib> 15 #include <fstream> 16 #include <sstream> 17 #include <algorithm> 18 #include <map> 19 #include <set> 20 #include <stack> 21 #include <queue> 22 #include <vector> 23 #include <stack> 24 #ifndef WIN32 25 #define Auto "%lld" 26 #else 27 #define Auto "%I64d" 28 #endif 29 using namespace std; 30 typedef bool boolean; 31 const signed int inf = (signed)((1u << 31) - 1); 32 const double eps = 1e-6; 33 const int binary_limit = 128; 34 #define smin(a, b) a = min(a, b) 35 #define smax(a, b) a = max(a, b) 36 #define max3(a, b, c) max(a, max(b, c)) 37 #define min3(a, b, c) min(a, min(b, c)) 38 template<typename T> 39 inline boolean readInteger(T& u){ 40 char x; 41 int aFlag = 1; 42 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 43 if(x == -1) { 44 ungetc(x, stdin); 45 return false; 46 } 47 if(x == ‘-‘){ 48 x = getchar(); 49 aFlag = -1; 50 } 51 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 52 ungetc(x, stdin); 53 u *= aFlag; 54 return true; 55 } 56 57 ///map template starts 58 typedef class Edge{ 59 public: 60 int end; 61 int next; 62 Edge(const int end = 0, const int next = 0):end(end), next(next){} 63 }Edge; 64 65 typedef class MapManager{ 66 public: 67 int ce; 68 int *h; 69 Edge *edge; 70 MapManager(){} 71 MapManager(int points, int limit):ce(0){ 72 h = new int[(const int)(points + 1)]; 73 edge = new Edge[(const int)(limit + 1)]; 74 memset(h, 0, sizeof(int) * (points + 1)); 75 } 76 inline void addEdge(int from, int end){ 77 edge[++ce] = Edge(end, h[from]); 78 h[from] = ce; 79 } 80 inline void addDoubleEdge(int from, int end){ 81 addEdge(from, end); 82 addEdge(end, from); 83 } 84 Edge& operator [] (int pos) { 85 return edge[pos]; 86 } 87 inline void clear() { 88 delete[] edge; 89 delete[] h; 90 } 91 }MapManager; 92 #define m_begin(g, i) (g).h[(i)] 93 ///map template ends 94 95 int n, m; 96 MapManager g; 97 int* dag; 98 int* dep; 99 100 inline boolean init() {101 if(!readInteger(n)) return false;102 readInteger(m);103 g = MapManager(n, m);104 dag = new int[(n + 1)];105 dep = new int[(n + 1)];106 memset(dag, 0, sizeof(int) * (n + 1));107 memset(dep, -1, sizeof(int) * (n + 1));108 for(int i = 1, a, b; i <= m; i++) {109 readInteger(a);110 readInteger(b);111 g.addEdge(b, a);112 dag[a]++;113 }114 return true;115 }116 117 queue<int> que;118 inline void topu() {119 for(int i = 1; i <= n; i++)120 if(!dag[i])121 dep[i] = 888, que.push(i);122 while(!que.empty()) {123 int e = que.front();124 que.pop();125 for(int i = m_begin(g, e); i; i = g[i].next) {126 int& eu = g[i].end;127 dag[eu]--;128 smax(dep[eu], dep[e] + 1);129 if(!dag[eu])130 que.push(eu);131 }132 }133 }134 135 int res;136 inline void solve() {137 res = 0;138 topu();139 for(int i = 1; i <= n; i++) {140 if(dag[i]) {141 puts("-1");142 return;143 }144 res += dep[i];145 }146 printf("%d\n", res);147 }148 149 inline void clear() {150 g.clear();151 delete[] dep;152 delete[] dag;153 }154 155 int main() {156 while(init()) {157 solve();158 clear();159 }160 return 0;161 }
hdu 2647 Reward - 拓扑排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。