HDU.2647 Reward(拓扑排序 TopSort)

HDU.2647 Reward(拓扑排序 TopSort)

题意分析

裸的拓扑排序 详解请移步 算法学习 拓扑排序（TopSort） 这道题有一点变化是要求计算最后的金钱数。最少金钱值是888，最少的差额是1，如1号的人比2号钱要多，2号至少是1号人的钱数+1.根据拓扑排序的思想，我们只需要类比二叉树的层序遍历，每次取出入度为0的节点做处理，累加金钱数量，然后再取出入度为0的节点处理。直到取出所有的点或者判断成环即可。

代码总览

#include <iostream> #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <sstream> #include <set> #include <map> #include <queue> #include <stack> #include <cmath> #define nmax 10005 #define MEM(x) memset(x,0,sizeof(x)) using namespace std; int n,m; int indegree[nmax]; vector<int> v[nmax]; int cnt = 0; int tot = 0; bool suc = true; void topsort() { queue<int> q; int cal = 0; while(1){ for(int i = 1;i<=n;++i){ if(indegree[i] == 0){ q.push(i); cnt++; tot+=888+cal; indegree[i] = -1; } } if(q.empty()) break; while(!q.empty()){ int t = q.front();q.pop(); for(int i = 0; i<v[t].size();++i){ int tt = v[t][i]; if(indegree[tt] == -1){ suc = false; break; }else indegree[tt] --; } if(!suc) break; } if(!suc) break; cal++; } if(suc && cnt != n) suc = false; } int main() { //freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m) !=EOF){ suc = true;MEM(indegree);cnt = 0;tot = 0; for(int i = 1; i<=n;++i) v[i].clear(); for(int i = 0; i<m;++i){ int a,b; scanf("%d%d",&a,&b); indegree[a]++; v[b].push_back(a); } topsort(); if(suc){ printf("%d\n",tot); }else printf("-1\n"); } return 0; }